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

问题描述：

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

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

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

解题思路：

本题是一道典型的广度优先搜索 (BFS) 问题。我们从起点开始，每次向周围八个方向扩散，直到到达终点为止。同时，我们需要记录走过的路径长度，以便最后返回最短路径长度。

具体实现时，我们可以使用一个队列来存储当前还未遍历的节点。每次从队列中取出一个节点，然后向周围八个方向扩散，将符合条件的节点加入队列中。同时，我们需要使用一个 visited 数组来记录每个节点是否已经被遍历过了，以防止重复遍历。

代码实现：

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 pathLength = 1;
        int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 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;
    }
}

代码解析：

首先判断输入矩阵是否为空或无效。
初始化 visited 数组和队列，将起点加入队列。
定义 directions 数组，存储八个方向的偏移量。
循环遍历队列，直到队列为空。
每次从队列中取出一个节点，并检查是否到达终点。
如果未到达终点，则向周围八个方向扩散，将符合条件的节点加入队列。
更新路径长度 pathLength。
如果队列为空，则表示不存在畅通路径，返回 -1。

总结：

本文介绍了使用 Java 实现二进制矩阵最短畅通路径算法的思路和代码，并详细解释了广度优先搜索 (BFS) 的应用。通过代码实现，我们可以清晰地理解 BFS 的原理和应用场景。