解法
01-BFS. 移動A のコストが 0, 移動B のコストが 1. Queue の代わりに deque を用いる.
コスト 0の方が優先されるので,queue の先頭に入れる. コスト 1は後回しなので,,queue の後ろに入れる.
実装の注意
移動 Bのとき,移動先として今いるマスは除外してもよい. ただし,変化量 0を除外するタイミングに注意.
for dr in [-2, 2] // ここでは,まだ dr = 0 は除外しない
for dc in [-2, 2] // ここでは,まだ dc = 0 は除外しない
if(dr == 0 && dc == 0) continue;
の様になる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll h,w; cin >> h >> w;
vll src(2),tar(2);
rep(i,2) cin >> src[i], src[i]--;
rep(i,2) cin >> tar[i], tar[i]--;
cinv(s);
const ll inf = h*w + 5;
vvll dis(h, vll(w,inf));
deque<pll> q;
auto push = [&](ll r, ll c, ll d, ll type) -> void {
if(!in(r,h)) return;
if(!in(c,w)) return;
if(s[r][c] == '#') return;
if(chmin(dis[r][c], d)){
if(type == 1) q.push_back({r,c});
else q.push_front({r,c});
}
};
push(src[0], src[1], 0, 1);
while(q.size()){
auto [r,c] = q.front(); q.pop_front();
ll d = dis[r][c];
// 0
{
vll dr = {1,0,-1,0};
vll dc = {0,1,0,-1};
rep(i,4){
push(r + dr[i], c + dc[i], d, 0);
}
}
// 1
srep(dr,-2,3) { // WA: if(dr): dr == 0 && dc != 0 を除外してしまうため
srep(dc,-2,3) { // WA: if(dc): dc == 0 && dr != 0 を除外してしまうため
if(dr == 0 && dc == 0) continue; // 無くてもよい
push(r + dr, c + dc, d + 1, 1);
}
}
}
ll ans = dis[tar[0]][tar[1]];
if(ans == inf) ans = -1;
cout << ans << endl;
return 0;
}