BFS题解

?第一篇题解？

【题意分析】

本题要求我们找到从起点 $(sx,sy)$ 到终点 $(gx,gy)$ 的最短路径，由于广搜算法本身就能找到迷宫中任意两点的（保证走通）最短路径，因此可以直接套用模板，在抵达终点后输出此时的步数即可。

【正确代码】

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,gx,gy;
char a[55][55];
bool vis[55][55];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
struct node{
    int x,y,step; //坐标与步数
};
void bfs(){
    queue<node> q;
    q.push({sx,sy,0});
    vis[sx][sy]=true;
    while(q.size()){
        node now=q.front();
        q.pop();
        if(now.x==gx&&now.y==gy){ //找到终点，输出答案，算法停止
            cout<<now.step;
            return ;
        }
        for(int i=0;i<4;i++){
            int nx=now.x+dx[i],ny=now.y+dy[i];
            if(nx<0||nx>n+1||ny<0||ny>m+1) continue;
            if(vis[nx][ny]||a[nx][ny]=='#') continue;
            vis[nx][ny]=true;
            q.push({nx,ny,now.step+1}); //每一步都是上一步的步数加一
        }
    }
}
signed main(){
    cin>>n>>m>>sx>>sy>>gx>>gy;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
    bfs();
    return 0;
}

【复杂度分析】

时间复杂度： $O(m \times n)$
空间复杂度： $O(m \times n)$
对于 $1≤n,m≤50$ 可完全接受

【预计得分】

$100pts$