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

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

本文介绍了使用广度优先搜索 (BFS) 算法求解二进制矩阵中最短畅通路径的思路和 Java 代码实现。畅通路径是指从左上角到右下角的路径，且路径上的所有单元格值为 0，相邻单元格在八个方向之一上连通。

解题思路：

本题可以使用广度优先搜索（BFS）来解决。我们从起点 (0, 0) 开始，每次将当前位置的上下左右斜八个方向的点加入队列中，并将其距离加 1。如果到达终点，返回距离即可。需要注意的是，需要记录已经访问过的点，以避免重复访问。

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[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1}); // {x, y, distance}
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            if (curr[0] == n - 1 && curr[1] == n - 1) {
                return curr[2];
            }
            for (int[] dir : dirs) {
                int x = curr[0] + dir[0];
                int y = curr[1] + dir[1];
                if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 && !visited[x][y]) {
                    visited[x][y] = true;
                    queue.offer(new int[]{x, y, curr[2] + 1});
                }
            }
        }
        return -1;
    }
}

代码解释：

1. 首先判断输入是否合法，如果起点或终点为 1，则不存在路径，直接返回 -1。
2. 定义一个数组 dirs 来存储八个方向的偏移量。
3. 创建一个队列 queue 来存储待访问的节点，初始状态只包含起点 (0, 0) 和距离 1。
4. 创建一个二维数组 visited 来记录已经访问过的节点，初始状态所有节点都未被访问。
5. 循环遍历队列，每次取出队首节点，并将其八个方向的相邻节点加入队列，同时更新距离。
6. 如果到达终点，则返回距离。
7. 如果遍历完队列仍然没有到达终点，则不存在路径，返回 -1。

**时间复杂度：**O(n^2)，其中 n 是矩阵的边长。

**空间复杂度：**O(n^2)，主要是用来存储 visited 数组。

优化建议：

• 可以使用双端队列来优化 BFS，在某些情况下可以提高效率。
• 可以使用更简洁的代码来实现 BFS 算法，例如使用迭代器来遍历队列。
• 可以使用其他算法来解决该问题，例如 A* 算法。

总结：

本文介绍了使用 BFS 算法求解二进制矩阵中最短畅通路径的思路和 Java 代码实现，并给出了优化建议。希望本文能够帮助读者更好地理解 BFS 算法的应用。