題目分析

來源：acwing

分析：

dfs分兩類，一類是內(nèi)部搜索，不需要恢復(fù)現(xiàn)場；一類是外部搜索（以整個圖作為狀態(tài)），需要恢復(fù)現(xiàn)場。這里的馬走日就是狀態(tài)圖，需要恢復(fù)現(xiàn)場。

理清dfs，需要畫一個搜索樹。

馬走日的8個方向

int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 10; int n, m; bool st[N][N]; int ans;int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; //第三個參數(shù)表示當(dāng)前在搜第幾個數(shù) void dfs(int x, int y, int cnt){// 在搜第n *m 個點if( cnt == n * m){ans ++;return;}st[x][y]= true;for(int i = 0; i < 8; i ++){int a = x + dx[i], b = y + dy[i];if( a < 0 || a >= n || b < 0 || b >= m || st[a][b]) continue;dfs(a, b, cnt + 1); // DFS轉(zhuǎn)移}// 恢復(fù)現(xiàn)場st[x][y] = false; }int main(){int T;cin >> T;while(T--){int x, y;cin >> n>> m >> x >> y;ans = 0;dfs(x, y, 1); // 第三個參數(shù)：在搜第幾個點cout << ans << endl;}}

題目來源

https://www.acwing.com/problem/content/1118/

總結(jié)

以上是生活随笔為你收集整理的算法提高课-搜索-DFS之搜索顺序-AcWing 1116. 马走日：dfs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。