AKSZ-BFS
2024-05-19 17:28:47
发布于:广东
4阅读
0回复
0点赞
广度优先搜索
模板
#include<bits/sdtc++.h>
using namespace std;
const int maxn = 45;
int n, m;
char s[maxn][maxn];
//方向数组
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int vis[maxn][maxn]; //每个点不重复
//状态 在哪个点,目前使用步数
//结构体定义状态
struct node{
int x, y; //目前走到(x, y)这个点上
int step;
};
void bfs(){
//维护一个队列 -> 扩展状态
queue<node> q; //状态队列
//先让出发点入队
q.push(node{0, 0, 0}); //将0, 0, 0状态入队
vis[0][0] = 1;
//队列非空,更新状态
while(!q.empty()){
node tmp = q.front(); //取出队列头
q.pop(); //出队
if(tmp.x == n - 1 && tmp.y == m - 1){
cout << tmp.step << endl;
return; //第一个找到
}
for(int i = 1; i <= 4; i++){
int tx = tmp.x + dx[i]; //下一步x坐标
int ty = tmp.y + dy[i]; //下一步y坐标
if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue; //越界跳过
if(vis[tx][ty]) continue; //每个点访问一次
if(s[tx][ty] == '#') continue; //遇到障碍跳过
vis[tx][ty] = 1; //表示已访问
q.push(node{tx, ty, tmp.step + 1}) //入队状态
}
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> s[i][j];
bfs();
return 0;
}
单调性
B站关注Regenfallen
全部评论 1
very good
2024-05-19 来自 广东
0
有帮助,赞一个