最短経路問題

これまであまり解いてこなかった最短経路問題を解いたので、今後の参考のため、ここに実装したコードを残しておく。

問題は以下。
https://leetcode.com/problems/shortest-path-in-binary-matrix/

解答コードは以下。競技プロ界ではお馴染みの BFS を使用している。

    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0] == 1) {
            return -1;
        }

        int bottomEnd = grid.length - 1;
        int rightEnd = grid[0].length - 1;
        Queue<Point> queue = new LinkedList<>();

        int[] dx = new int[]{1, 1, 0, -1, -1, -1, 0, 1};
        int[] dy = new int[]{0, 1, 1, 1, 0, -1, -1, -1};

        // 始点をキューに入れる。
        queue.add(new Point(0, 0));
        grid[0][0] = 1;
        int level = 1;

        while(queue.size() > 0) {
            // 同階層を処理する。
            // 始点から 1 手で行ける地点：level 1
            // 始点から 2 手で行ける地点：level 2
            // 始点から n 手で行ける地点：level n
            int curLevelSize = queue.size();
            for(int i = 0; i < curLevelSize; i++) {
                Point cur = queue.poll();

                // 終了条件
                if(cur.x == bottomEnd && cur.y == rightEnd) {
                    return level;
                }

                for(int j = 0; j < 8; j++) {
                    int neighborX = cur.x + dx[j];
                    int neighborY = cur.y + dy[j];
                    if((0 <= neighborX && neighborX <= bottomEnd) &&
                            (0 <= neighborY && neighborY <= rightEnd) &&
                            grid[neighborX][neighborY] == 0) {
                        // 訪問済みを 1 にしてキューに入れる。
                        // そうしないと、同階層のものを再度キューに入れることになり得る。
                        grid[neighborX][neighborY] = 1;
                        queue.add(new Point(neighborX, neighborY));
                    }
                }
            }

            // 同階層を一通り処理したので、level をカウントアップ。
            level++;
        }
        return -1;
    }

    private class Point {
        int x; // 2次元配列の1個目(行)
        int y; // 2次元配列の2個目(列)

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }