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

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

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

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

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

解题思路：

本题可以使用广度优先搜索（BFS）求解最短路径。

首先，我们需要确定起点和终点，起点为左上角单元格，终点为右下角单元格。
其次，我们需要定义一个队列，用于存储待访问的单元格。将起点加入队列中。
然后，我们需要定义一个二维数组，用于记录每个单元格是否已经访问过。初始时，所有单元格都未被访问过。我们可以使用布尔类型的二维数组visited来记录。
接下来，我们进入BFS的循环。每次循环，我们从队列中取出一个单元格，然后检查它周围的8个单元格是否符合要求。如果符合要求且未被访问过，则将其加入队列中，并标记为已访问。
最后，如果我们能够访问到终点，那么返回路径长度。如果无法访问到终点，返回-1。

Java代码实现：

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

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            return -1; // 起点或终点不可达
        }

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        boolean[][] visited = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0}); // 起点入队
        visited[0][0] = true;
        int pathLength = 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; // 到达终点
                }

                // 遍历8个方向
                for (int[] dir : directions) {
                    int newRow = row + dir[0];
                    int newCol = col + 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; // 无法到达终点
    }
}

代码解释:

shortestPathBinaryMatrix(int[][] grid): 该函数接受一个二维整数数组grid作为输入，表示二进制矩阵，并返回最短畅通路径的长度。
directions: 定义了8个方向的偏移量。
visited: 用于记录每个单元格是否被访问过。
queue: 使用队列实现BFS。
代码首先检查起点和终点是否可达。如果不可达，则直接返回-1。
随后，将起点加入队列，并标记为已访问。
在BFS循环中，每次从队列中取出一个单元格，并遍历其周围8个方向的单元格。
如果相邻单元格符合要求（坐标合法、值为0、未被访问过），则将其加入队列，并标记为已访问。
如果在遍历过程中到达了终点，则返回当前路径长度。
如果遍历完所有可达单元格后仍未找到终点，则返回-1，表示不存在畅通路径。

希望以上内容能够帮助您理解如何在Java中找到二进制矩阵中最短畅通路径长度。