Java 实现二进制矩阵中最短畅通路径

问题描述： 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短畅通路径的长度。如果不存在这样的路径，返回 -1 。二进制矩阵中的畅通路径是一条从左上角单元格（即，(0, 0)）到右下角单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

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

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

解题思路：

本题可以使用广度优先搜索（BFS）来求解最短路径。从起点开始，每次将周围未访问过的节点加入队列中，直到到达终点或者队列为空。为了避免重复访问，我们需要使用一个 visited 数组来记录每个节点是否已经被访问过。

Java 代码实现：

class Solution {
    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 = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        int pathLength = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                if (curr[0] == n - 1 && curr[1] == n - 1) {
                    return pathLength;
                }
                for (int[] dir : directions) {
                    int nextX = curr[0] + dir[0];
                    int nextY = curr[1] + dir[1];
                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && grid[nextX][nextY] == 0 && !visited[nextX][nextY]) {
                        queue.offer(new int[]{nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
            pathLength++;
        }
        return -1;
    }
}

代码说明：

首先，判断输入是否合法，例如 grid 是否为空、起点或终点是否为 1 等。
初始化 visited 数组、队列和方向数组。
将起点加入队列，并将起点标记为已访问。
使用循环遍历队列，每次取出队列首元素，并检查其周围 8 个方向的节点是否满足条件，如果满足条件则将其加入队列并标记为已访问。
如果当前节点为终点，则返回路径长度。
如果队列为空，则说明不存在畅通路径，返回 -1。

总结：

本代码使用广度优先搜索算法，通过遍历所有可能路径，找到最短畅通路径的长度。代码清晰易懂，结构简单，易于理解和实现。