AKSZ-广度优先搜索
2024-05-19 17:37:31
发布于：广东
6阅读
0回复
0点赞
广度优先搜索
模板
#include<bits/stdc++.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];
//状态 在哪个点，目前使用 step 步数
//结构体定义状态
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();
}
有帮助，赞一个