状態を持たせたBFS. (そのマスに辿り着いた方向) \(\in 4\) を記録しながら BFS.
実装
安全に行くなら，ルール通りに遷移する． つまり，一気に何マスも移動できる様に実装する． これは while 文で良い．
TLE には注意．枝狩をするには，そのマスに辿り着いた方向 \(\in 4\) を 覚えておけば十分．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll dis[1505][1505][5];
bool vis[1505][1505][5];
int main() {
ll h,w;
ll n ; cin >> n;
vll a(2), b(2);
cinv(a);
cinv(b);
rep(i,2){
a[i]--;
b[i]--;
}
h = n, w = n;
cinv(s);
auto valid = [&](ll x, ll y) -> bool {
return in(x,h) && in(y,w) && (s[x][y]!='#');
};
using T = tuple<ll,ll,ll>;
auto bfs = [&](ll sx, ll sy) -> void {
queue<T> que;
auto push = [&](ll x, ll y, ll r, ll d) -> void {
vis[x][y][r] = true;
dis[x][y][r] = d;
que.push({x,y,r});
};
push(sx, sy, 4, 0);
while(que.size()){
auto [x,y,r] = que.front(); que.pop();
ll d = dis[x][y][r];
vll dx = {-1,1,1,-1};
vll dy = {-1,-1,1,1};
rep(nr,4) {
ll nx = x;
ll ny = y;
while(true){
nx += dx[nr];
ny += dy[nr];
if(!valid(nx,ny)) break;
if(vis[nx][ny][nr]) break;
push(nx, ny, nr, d+1);
}
}
}
};
bfs(a[0], a[1]);
ll ans = INFL;
rep(r,4){
if(vis[b[0]][b[1]][r])
chmin(ans, dis[b[0]][b[1]][r]);
}
if(ans >= INFL) ans = -1;
cout << ans << endl;
return 0;
}
