算法提高课-搜索-DFS之连通性模型-AcWing 1112. 迷宫：dfs和bfs两种解法

题目分析

来源：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;} }

题目来源

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的算法提高课-搜索-DFS之连通性模型-AcWing 1112. 迷宫：dfs和bfs两种解法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。