【題解】AtCoder ABC176D – Wizard in Maze

#include <iostream>
#include <queue>
using namespace std;

int h, w, g[1005][1005], ans[1005][1005], vis[1005][1005], ch, cw, dh, dw;
string s;

int main() {
    cin >> h >> w;
    cin >> ch >> cw >> dh >> dw;
    for (int i = 1; i <= h; i++){
        cin >> s;
        for (int j = 1; j <= w; j++){
            if (s[j-1] == '.') g[i][j] = 1;
        }
    }
    priority_queue <pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > pq;
    pq.push({0, {ch, cw}});
    while (!pq.empty()){
        int d = pq.top().first, x = pq.top().second.first, y = pq.top().second.second;
        pq.pop();
        if (vis[x][y]) continue;
        ans[x][y] = d;
        vis[x][y] = 1;
        for (int i = max(1, x-2); i <= min(h, x+2); i++){
            for (int j = max(1, y-2); j <= min(w, y+2); j++){
                if (!g[i][j] || vis[i][j]) continue;
                if (abs(i-x)+abs(j-y) == 1){
                    ans[i][j] = ans[x][y];
                    pq.push({ans[i][j], {i, j}});
                }
                else{
                    ans[i][j] = ans[x][y]+1;
                    pq.push({ans[i][j], {i, j}});
                }
            }
        }
    }
    if (!vis[dh][dw]) cout << -1 << "\n";
    else cout << ans[dh][dw] << "\n";
}