[ABC246] E - Bishop 2

[Q] https://atcoder.jp/contests/abc246/tasks/abc246_e

1. BFSをしよう
2. 方向を決めて、壁かポーンに当たるまで直進しつづける。
3. もしかして、飛び越す場合も考慮しないといけないかも？
(3手目で、1手目の交差点を飛び越える場合)

4. 毎回 2. を見ると、TLEしちゃうかも？
5. 方向ごとに、見たかどうか
bool seen[][][4]
を用意すれば、飛び越え(3)を見つつ重複探索(4)を省けそうだ。

Q. 飛び越える場合ある？
A. もしかしたら、ないかも？1手目でいけるなら、2手目で見るはずだから。

実装

ll N;
ll sy, sx, gy, gx;
char C[1510][1510];
ll DP[1510][1510];
bool seen[1510][1510][4];

int main() {
 cincout();

 cin >> N >> sy >> sx >> gy >> gx;
 --sy, --sx, --gy, --gx;
 rep(i, N) { cin >> C[i]; }
 if ((abs(sy - gy) + abs(sx - gx)) % 2 == 1) {
   cout << -1 << endl;
   return 0;
 }
 rep(i, N) rep(j, N) { DP[i][j] = oo; }

 queue<pll> Q;
 Q.push({sy, sx});
 DP[sy][sx] = 0;
 ll turn = 0;
 while (!Q.empty()) {
   if (DP[gy][gx] != oo) break;
   ll qsz = Q.size();
   ++turn;
   rep(i, qsz) {
     auto [y, x] = Q.front();
     Q.pop();
     rep(d, 4) { // 方向きめて、
       for (ll k = 1; k < N; ++k) { // 直進し続ける
         ll ny = y + dy[d] * k;
         ll nx = x + dx[d] * k;
         if (isn_field(ny, nx, N, N)) break; // field外ならおしまい
         if (C[ny][nx] == '#') break; // ポーンならおしまい
         if (seen[ny][nx][d]) break; // その方向への探索をしたことがあるならおしまい
         seen[ny][nx][d] = true;
         if (chmin(DP[ny][nx], turn)) {
           Q.push({ny, nx});
         }
       }
     }
   }
 }
 if (DP[gy][gx] == oo) DP[gy][gx] = -1;
 cout << DP[gy][gx] << endl;
}

https://atcoder.jp/contests/abc246/submissions/30658328