网站建设外包还是自建,网站建设方案平台,网页设计尺寸大小,成都网络关键词排名第四题#xff1a;T4迷宫
标签#xff1a;宽度优先搜索题意#xff1a;给定 n n nx m m m由 # \# ##xff08;墙#xff09;、 . . .#xff08;空地#xff09;组成的地图#xff0c;求从左上角到右下角的最少步数#xff0c;每次只允许上下左右移动一格#xff0…第四题T4迷宫
标签宽度优先搜索题意给定 n n nx m m m由 # \# #墙、 . . .空地组成的地图求从左上角到右下角的最少步数每次只允许上下左右移动一格不允许走出地图和走到 # \# #墙上。题解BFS 模板题判断下一个能否走的点经典三要素
下个点是否是障碍物宽泛来说是题目中的限制条件下个点是否走过避免死循环下个点是否在地图内
代码
#include bits/stdc.h
using namespace std;int n, m;
int dx[4] {0, 0, -1, 1};
int dy[4] {-1, 1, 0, 0};char a[1005][1005];
bool vis[1005][1005];
struct node {int x, y, step;
};void bfs() {queue node q;vis[1][1] 1;q.push({1, 1, 0});while (!q.empty()) {node u q.front();q.pop();if (u.x n u.y m) {cout u.step endl;return ;}for (int i 0; i 4; i) {int nx u.x dx[i];int ny u.y dy[i];if (nx 1 || nx n || ny 1 || ny m) continue;if (vis[nx][ny] || a[nx][ny] #) continue;vis[nx][ny] 1;q.push({nx, ny, u.step 1});}}cout No solution endl;
}int main() {cin n m;for (int i 1; i n; i)for (int j 1; j m; j)cin a[i][j];bfs();return 0;
}
