題目分析

來源：acwing

分析：

dfs是一路搜下去，不撞南墻不回頭。

dfs解法

#include<bits/stdc++.h> using namespace std; const int N = 110; char g[N][N]; bool st[N][N]; int n; int xa, ya, xb, yb;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};bool dfs(int x, int y){if(g[xa][ya] == '#' || g[xb][yb] == '#') return false;if( x == xb && y == yb) return true;st[x][y]= true;for(int i = 0; i < 4; i ++){int a = x + dx[i], b = y + dy[i];if( a < 0 || a >= n || b < 0 || b >= n || st[a][b] || g[a][b] == '#') continue;if(dfs(a,b)) return true;}return false; }int main(){int T;cin >> T;while( T --){cin >>n;for(int i = 0; i < n; i ++) cin >> g[i];memset(st, 0, sizeof st);cin >> xa >> ya >> xb >> yb;if(dfs(xa,ya)) puts("YES");else puts("NO");} }

bfs解法

#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int N = 110, M = N * N; PII q[M]; // 注意隊列不要開小了 char g[N][N]; bool st[N][N]; int n; bool bfs(int sx, int sy, int tx, int ty){if(g[sx][sy] == '#' || g[tx][ty] == '#') return false;if( sx == tx && sy == ty) return true;memset(st, 0, sizeof st);int dx[4] = { -1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int hh = 0, tt =0;q[0] = {sx, sy};st[sx][sy] = true;while( hh <= tt){PII t = q[ hh ++];for(int i = 0; i< 4; i ++){int a = t.x + dx[i], b = t.y + dy[i];if( a < 0 || a >=n || b < 0 || b >= n || st[a][b] || g[a][b] == '#') continue;if( a == tx && b == ty) return true;st[a][b] = true;q[++ tt] = {a, b}; }}return false;}int main(){int T;cin >> T;while(T--){cin >> n;for(int i = 0; i < n; i ++) cin >> g[i];int sx,sy, tx,ty;cin >> sx >> sy >> tx >> ty;if(bfs(sx,sy, tx, ty)) cout << "YES" << endl;else cout << "NO" << endl;} }

題目來源

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的算法提高课-搜索-DFS之连通性模型-AcWing 1112. 迷宫：dfs和bfs两种解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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