题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int MAXN = 1005;
const int INF = 1e9;

char g[MAXN][MAXN];
int dist[MAXN][MAXN];
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};

int main(){
int h, w, ch, cw, dh, dw;
scanf("%d%d%d%d%d%d", &h, &w, &ch, &cw, &dh, &dw);
ch--; cw--; dh--; dw--;
for(int i = 0; i < h; i++) scanf("%s", g[i]);
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++) dist[i][j] = INF;
deque<pair<int,int>> dq;
dist[ch][cw] = 0;
dq.push_front({ch, cw});
while(!dq.empty()){
auto [r, c] = dq.front(); dq.pop_front();
int d = dist[r][c];
if(r == dh && c == dw) break;
// 步行 (代价 0): 入队头
for(int k = 0; k < 4; k++){
int nr = r + dr[k], nc = c + dc[k];
if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if(g[nr][nc] == '#') continue;
if(dist[nr][nc] > d){
dist[nr][nc] = d;
dq.push_front({nr, nc});
}
}
// 魔法 (代价 1): 5×5 范围内所有道路格, 入队尾
for(int dr2 = -2; dr2 <= 2; dr2++){
for(int dc2 = -2; dc2 <= 2; dc2++){
if(dr2 == 0 && dc2 == 0) continue;
int nr = r + dr2, nc = c + dc2;
if(nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if(g[nr][nc] == '#') continue;
if(dist[nr][nc] > d + 1){
dist[nr][nc] = d + 1;
dq.push_back({nr, nc});
}
}
}
}
printf("%d\n", dist[dh][dw] == INF ? -1 : dist[dh][dw]);
return 0;
}