AKSZ-广度优先搜索
2024-05-31 15:30:51
发布于：广东
15阅读
0回复
0点赞
广度优先搜索
模板（acgo T22419 迷宫）
#include<bits/stdc++.h>
using namespace std;
//模板
int n,m;
char s[45][45];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};//方向数组//
int vis[45][45];
//结构体定义状态
struct node{
int 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=0;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=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>s[i][j];
}
}
bfs();
return 0;
}
有帮助，赞一个