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

问题描述：

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

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

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

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

解题思路：

本题是一道典型的 BFS 最短路径问题。我们可以从起点 (0, 0) 开始进行 BFS，每次将当前位置的上下左右以及斜向上下左右的位置加入队列中，直到找到终点位置 (n-1, n-1) 或者队列为空。

需要注意的是，在每次加入队列的时候，需要将当前位置标记为已访问，避免重复访问。同时，由于本题中的矩阵中的值为二进制，因此需要将当前位置的值与 0 进行比较，判断是否可以通行。

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;
        int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        int steps = 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 steps;
                }

                for (int[] dir : directions) {
                    int row = curr[0] + dir[0];
                    int col = curr[1] + dir[1];
                    if (row >= 0 && row < n && col >= 0 && col < n && grid[row][col] == 0 && !visited[row][col]) {
                        queue.offer(new int[]{row, col});
                        visited[row][col] = true;
                    }
                }
            }
            steps++;
        }

        return -1;
    }
}

解释：

首先，判断输入矩阵是否合法。如果矩阵为空、长度为 0、起点或终点为 1，则返回 -1，表示不存在畅通路径。
定义 directions 数组，用于存储 8 个方向的偏移量。
定义 visited 数组，用于记录每个单元格是否被访问过。
使用 queue 存储待访问的单元格坐标。
将起点 (0, 0) 加入队列，并将起点标记为已访问。
使用循环遍历队列，每次取出队列头部的单元格，并将该单元格的 8 个方向上的相邻单元格加入队列，并将这些单元格标记为已访问。
如果找到终点 (n-1, n-1)，则返回当前步数，即最短路径的长度。
如果循环结束后，队列为空，则表示没有找到终点，返回 -1。

代码优化：

可以使用 HashSet 或 HashMap 来存储已访问的单元格，以提高查找效率。
可以使用 PriorityQueue 来存储待访问的单元格，并根据距离排序，以优先访问距离起点较近的单元格，从而提高算法效率。

总结：

本文介绍了使用 Java 代码实现二进制矩阵中从左上角到右下角最短畅通路径的算法，并详细讲解了 BFS 算法的思路以及代码实现。您可以根据具体需求对代码进行优化。