Java 查找二进制矩阵中的最短畅通路径

Java 查找二进制矩阵中的最短畅通路径

给定一个 n x n 的二进制矩阵 grid，返回矩阵中最短畅通路径的长度。如果不存在这样的路径，返回 -1。

二进制矩阵中的畅通路径是一条从左上角单元格（即，(0, 0)）到右下角单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

• 路径途经的所有单元格的值都是 0。
• 路径中所有相邻的单元格应当在 8 个方向之一上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度是该路径途经的单元格总数。

解题思路

本题可用 BFS 解决。首先需要将起点 (0, 0) 入队，然后每次取出队首元素，从该元素的八个方向中寻找值为 0 的位置，将其入队，并将该位置的值更新为已访问过。直到队列为空或者到达终点 (n-1, n-1)。

需要一个二维数组 visited 来记录每个位置是否已经被访问过，避免重复访问。

代码实现

public class ShortestPathInBinaryMatrix {

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

        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        int pathLength = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int row = current[0];
                int col = current[1];

                if (row == n - 1 && col == n - 1) {
                    return pathLength;
                }

                for (int[] direction : directions) {
                    int nextRow = row + direction[0];
                    int nextCol = col + direction[1];

                    if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 0 && !visited[nextRow][nextCol]) {
                        queue.offer(new int[]{nextRow, nextCol});
                        visited[nextRow][nextCol] = true;
                    }
                }
            }
            pathLength++;
        }

        return -1;
    }
}