题解 | 走迷宫

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

const int N = 1010;
int n,m,sx,sy,fx,fy;
char g[N][N];
int d[N][N];
bool vis[N][N];
queue<pair<int,int>> q;
int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};

void bfs(int sx,int sy){
    memset(d,0x3f,sizeof d);
    d[sx][sy] = 0;
    vis[sx][sy] = 1;
    q.push({sx,sy});

    while(q.size()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if(x==fx&&y==fy){
            cout<<d[x][y];
            return;
        }

        for(int i = 0;i<4;i++){
            int a = x + dx[i],b = y + dy[i];
            if(a<1||a>n||b<1||b>m) continue;
            if(d[a][b]<d[x][y]+1) continue;
            if(g[a][b]=='*'||vis[a][b]) continue;
            vis[a][b] = 1;
            d[a][b] = d[x][y] + 1;
            q.push({a,b});
        }
    }
    cout<<-1;
}

int main(){
    cin>>n>>m;
    cin>>sx>>sy>>fx>>fy;
    for(int i = 1;i<=n;i++) scanf("%s",g[i]+1);
    bfs(sx,sy);
    return 0;
}