BFS 迷宫问题

解题思路:

注意事项:

刚开始一直得到-1的结果TT 原来是下面这段代码的问题  这里要写！='#' 而不是=='-' 

if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&dis[nx][ny]==-1&&grid[nx][ny]!='#')

迷宫问题模板如下：

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
queue<pair<int,int>> q;
int grid[1000][1000];
int dis[1000][1000];
//bfs
int bfs(int startx,int starty,int endx,int endy){
    q.push({startx,starty});
    memset(dis,-1,sizeof(dis));  //-1看是否被访问过
    dis[startx][starty]=0;
    
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        //看看当前位置是不是出口，如果是出口就结束
        if(x==endx&&y==endy) return dis[x][y];
        //不是出口遍历四个方向
        for(int k=0;k<4;k++){
            //新的x和y坐标
            int nx=x+dx[k];
            int ny=y+dy[k];
            //判断该坐标是否在该地图内/是否被访问过/是否是通路
            if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&dis[nx][ny]==-1&&grid[nx][ny]==0){
                dis[nx][ny]=dis[x][y]+1; 
                q.push({nx,ny});  //该坐标可走，放到队列里面去
        }
    }
        
}

如果是要打印路径：

在 BFS 过程中，可以通过栈来模拟从目标节点回溯到起始节点的过程，这样就可以避免使用额外的二维数组来记录每个节点的前驱节点

void printpath(int startx,int starty,int endx,int endy){
    sack<pair<int,int>> path;  //只知道从后往前的路径
    int curx=endx,cury=endy;  //当前位置
    
    while(curx!=startx||cury!=starty){
        path.push({curx,cury});
        //找到当前节点的前一个结点
        for(int k=0;k<4;k++){
            int nx=curx+dx[k];
            int ny=cury+dy[k];
            if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&dis[nx][ny]==dis[curx][cury]-1){
                curx=nx;
                cury=ny;
                break;  //dis[nx][ny]==dis[curx][cury]-1 找到了上一步
            }
        }
    }
    //最后把起始点也放到栈里
    path.push({startx,starty});
    
    //输出路径
    while(!path.empty()){
        auto p=path.top();
        path.pop();
        cout<<"("<<p.first<<","<<p.second<<")"<<endl;
    }
}

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
char grid[1000][1000];    
int dis[1000][1000];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
queue<pair<int,int>> q;
int  bfs(int sx,int sy,int ex,int ey){
    memset(dis,-1,sizeof(dis));
    q.push({sx,sy});
    dis[sx][sy]=0;
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        if(x==ex&&y==ey) {
            
            return dis[x][y];
        }
        for(int k=0;k<4;k++){
            int nx=x+dx[k];
            int ny=y+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&dis[nx][ny]==-1&&grid[nx][ny]!='#'){
                dis[nx][ny]=dis[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    return -1;
    
}
int main()
{
    int T;
    while(cin>>T){
        while(T--){
            
            cin>>n>>m;
            int sx,sy,ex,ey;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    cin>>grid[i][j];
                    if(grid[i][j]=='S') {
                        sx=i;
                        sy=j;
                    }
                    if(grid[i][j]=='E'){
                        ex=i;
                        ey=j;
                    }
                }
            }
           int res= bfs(sx,sy,ex,ey);
           cout<<res<<endl;
        }
    }
    return 0;
}