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

给定一个 n x n 的二进制矩阵 grid，你需要找到从左上角单元格 (0, 0) 到右下角单元格 (n - 1, n - 1) 的最短畅通路径的长度。

二进制矩阵中的 畅通路径 是一条满足以下条件的路径：

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

如果不存在这样的路径，返回 -1 。

思路:

本题可以使用广度优先搜索（BFS）来解决。BFS 算法能够有效地找到从起点到终点的最短路径。

算法步骤：

将起点 (0, 0) 加入队列中，并将其标记为已访问。
当队列不为空时，执行以下操作：
- 从队列中取出一个节点。
- 如果该节点是终点 (n - 1, n - 1)，则返回当前步数。
- 否则，遍历该节点的 8 个相邻节点：
  - 如果相邻节点未越界、值为 0 且未被访问过，则将其加入队列，并标记为已访问。
如果队列为空，说明没有找到从起点到终点的路径，返回 -1。

Java代码：

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == 1) {
            return -1;
        }
        int n = grid.length;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0}); // 将起点加入队列
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true; // 标记起点已访问
        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) { // 遍历 8 个方向
                    int newRow = curr[0] + dir[0];
                    int newCol = curr[1] + dir[1];
                    if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] == 0 && !visited[newRow][newCol]) {
                        queue.offer(new int[]{newRow, newCol});
                        visited[newRow][newCol] = true;
                    }
                }
            }
            pathLength++;
        }
        return -1; // 无法到达终点
    }
}