AKSZ-广度优先搜素
2024-05-19 17:40:24
发布于：广东
15阅读
0回复
0点赞
广度优先搜素
BFS模板
#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];
struct node{
int x,y;
int step;
};
void bfs(){
queue<node>q;
q.push(node{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];
int ty=tmp.y+dy[i];
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});
}
}
return;
}
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;
}
有帮助，赞一个