题解 | 走迷宫

#include <bits/stdc++.h>
using namespace std;

int n,m,xs,ys,xt,yt;

vector<vector<char>> grid;
vector<vector<int>> dist;

int dfs(){
    queue<pair<int,int>> q;
    q.push({xs,ys});
    dist[xs][ys]=0;
    //上下左右
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    while(!q.empty()){
        auto current = q.front();
        q.pop();
        int x=current.first;
        int y=current.second;

        if(x==xt&&y==yt){
            return dist[x][y];//bfs得出路径必为最短路径
        }

        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<n && nx>=0 && ny<m && ny>=0 && grid[nx][ny]!='*' && dist[nx][ny]==-1){
                dist[nx][ny]=dist[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    return -1;
}

int main() {
    cin>>n>>m;
    cin>>xs>>ys>>xt>>yt;
    xs--;ys--;xt--;yt--;
    grid.resize(n,vector<char>(m));//初始化网格大小！否则会非法访问
    dist.resize(n,vector<int>(m,-1));//初始化距离为-1，同时作为未访问标记
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    if(grid[xt][yt]=='*'){
        cout<<-1;
        return 0;
    }
    int res;
    res=dfs();
    cout<<res;
    return 0;
}