AKSZ-bfs
2024-05-19 17:41:24
发布于:广东
广度优先搜索
#include<bits/stdc++.h>
using namespace std;
const int maxn=45;
int n,m,xx,yy,k;
char s[maxn][maxn];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};//方向数组
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状态入队
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});
}
}
}
int main(){
cin>>n>>m;
for(int i = 0;i<n;i++){
scanf("%s",s[i]);
}
bfs();
return 0;
}
这里空空如也
有帮助,赞一个