\(d[i][j]\) をマス \((i,j)\) に到達するために必要な最小手数と定義します。ただし、到達不可能な場合は十分大きい値 \(\text{inf}\) が入っているものとします。 (この問題では \(\text{inf}\) の値は \(10^7\) から \(10^9\) 程度が好ましいです。)

初期状態では \(d[sx][sy]=0\) 、それ以外は \(\text{inf}\) が入った状態です。ここから 01-BFS をすることで \(\text{inf}\) が入ったマスを更新することを考えます。

現在マス \((x,y)\) を見ているとします。01-BFS の遷移としてはここから \(1\) 手で移動できる場所の更新をしたいので、以下のように更新をすればいいことが分かります :

マス \((x,y)\) からマス \((x+k\times dx[i] , y+k\times dy[i])\) に移動可能ならば、 \(d[x+k\times dx[i]][y+k\times dy[i]]\) を \(d[x][y]+1\) との小さい方に更新する

ただし、 \((dx[i],dy[i])\) はビショップが進める方向をそれぞれ格納したものです。(より具体的には \(dx=\{1,-1,1,-1\},dy=\{1,1,-1,-1\}\))

以上の方針で 01-BFS を実装すると、以下のようなコードになります。

到達可能な間各マスを順に更新できるか確かめていき、更新できるなら更新に加えさらにそこを基準に他のマスも更新できないか確かめています。

実装例 (Java)

import java.util.*;

class Main {
    public static void main(String[] args) {
        var sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sx = sc.nextInt() - 1, sy = sc.nextInt() - 1;
        int gx = sc.nextInt() - 1, gy = sc.nextInt() - 1;
        var s = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            var t = sc.next();
            for (int j = 0; j < n; j++)
                s[i][j] = t.charAt(j) == '#';
        }
        var q = new ArrayDeque<Integer>();
        var d = new int[n][n];
        final int inf = (int) 1e7;
        for (var i : d)
            Arrays.fill(i, inf);
        d[sx][sy] = 0;
        q.add(sx);
        q.add(sy);
        int[] dx = { 1, -1, 1, -1 };
        int[] dy = { 1, 1, -1, -1 };
        while (!q.isEmpty()) {
            int x = q.remove();
            int y = q.remove();
            for (int i = 0; i < 4; i++) {
                int xx = x, yy = y;
                while (true) {
                    xx += dx[i];
                    yy += dy[i];
                    if (xx < 0 || xx >= n)
                        break;
                    if (yy < 0 || yy >= n)
                        break;
                    if (s[xx][yy])
                        break;
                    if (d[xx][yy] > d[x][y] + 1) {
                        d[xx][yy] = d[x][y] + 1;
                        q.add(xx);
                        q.add(yy);
                    }
                }
            }
        }
        System.out.println(d[gx][gy] == inf ? -1 : d[gx][gy]);
    }
}

しかし、このままだと TLE します。そこで、ここから高速化することを考えます。

更新していく際に \(d[x+k\times dx[i]][y+k\times dy[i]]\) が \(d[x][y]\) 以下であるようなマスに到達したとします。この場合、それ以降のマスの更新は既にマス \((x+k\times dx[i] , y+k\times dy[i])\) による探索により行われた、もしくはこれから行われるので見なくてもいいです。従って、そのようなマスがあった際は探索を打ち切ればいいです。

実装例 (Java)

import java.util.*;

class Main {
    public static void main(String[] args) {
        var sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sx = sc.nextInt() - 1, sy = sc.nextInt() - 1;
        int gx = sc.nextInt() - 1, gy = sc.nextInt() - 1;
        var s = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            var t = sc.next();
            for (int j = 0; j < n; j++)
                s[i][j] = t.charAt(j) == '#';
        }
        var q = new ArrayDeque<Integer>();
        var d = new int[n][n];
        final int inf = (int) 1e7;
        for (var i : d)
            Arrays.fill(i, inf);
        d[sx][sy] = 0;
        q.add(sx);
        q.add(sy);
        int[] dx = { 1, -1, 1, -1 };
        int[] dy = { 1, 1, -1, -1 };
        while (!q.isEmpty()) {
            int x = q.remove();
            int y = q.remove();
            for (int i = 0; i < 4; i++) {
                int xx = x, yy = y;
                while (true) {
                    xx += dx[i];
                    yy += dy[i];
                    if (xx < 0 || xx >= n)
                        break;
                    if (yy < 0 || yy >= n)
                        break;
                    if (s[xx][yy])
                        break;
                    if (d[xx][yy] > d[x][y] + 1) {
                        d[xx][yy] = d[x][y] + 1;
                        q.add(xx);
                        q.add(yy);
                    }
                    if (d[xx][yy] <= d[x][y])
                        break;
                }
            }
        }
        System.out.println(d[gx][gy] == inf ? -1 : d[gx][gy]);
    }
}

このコードで AC ができます。計算量は \(O(N^2)\) です。