题解 | #走迷宫#

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

const int N = 1010;
char g[N][N];
ll dist[N][N];
int n, m;
int xs, ys, xt, yt;

using pII = pair<int, int>;
pII q[N*N];// queue<pair<int, int>>q;
int hh = 0; int tt = -1; 

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int bfs() {
    q[++tt] = {xs,ys};// q.push({xs,ys});
    memset(dist,-1,sizeof(dist));
    dist[xs][ys] = 0;
    while(hh <= tt ){ //while(!q.empty())
        auto t = q[hh++];// auto t = q.front(); q.pop();
       
        for(int i = 0;i < 4; i++){
            int a = t.first+dx[i]; int b = t.second + dy[i];
            
            if(a<1||a>n||b<1||b>m) continue;
            if(g[a][b] == '*')continue;
            if(dist[a][b] >=0 ) continue;

            dist[a][b] = dist[t.first][t.second]+1;
            q[++tt] = {a,b}; //q.push({a,b});

            if(a == xt && b == yt) return dist[a][b];
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    cin >> xs >> ys >> xt >> yt;
    for(int i = 1;i<=n;i++){
        for(int j = 1; j <= m; j++){
            cin >> g[i][j];
        }
    }
    cout << bfs();
}