# 【題解】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";
}

```