Java: 最短畅通路径 - 二进制矩阵

Java: 在二进制矩阵中寻找最短畅通路径

在这篇文章中，我们将解决一个常见的面试算法问题：在一个 n x n 的二进制矩阵 grid 中，找到从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，则返回 -1。

问题描述:

在二进制矩阵中，'畅通路径'需要满足以下条件：

1. 路径上的所有单元格的值都为 0。2. 路径中所有相邻的单元格必须在 8 个方向之一上连接（水平、垂直或对角线）。

路径的长度定义为该路径经过的单元格总数。

解题思路：

我们可以使用广度优先搜索（BFS）算法来有效地解决这个问题。BFS 算法从起点开始，逐层向外扩展，直到找到终点或探索完所有可能的路径。

算法步骤：

1. 创建一个队列来存储待探索的单元格。2. 将起点 (0, 0) 加入队列，并将其标记为已访问。3. 初始化路径长度为 1。4. 当队列不为空时，执行以下操作： - 从队列中取出一个单元格。 - 如果该单元格是终点 (n-1, n-1)，则返回当前路径长度。 - 否则，探索该单元格的 8 个相邻单元格。 - 对于每个有效的相邻单元格（值为 0 且未被访问过）： - 将其标记为已访问。 - 将其加入队列。5. 如果队列为空且未找到终点，则表示不存在畅通路径，返回 -1。

**Java 代码实现:**javaimport java.util.LinkedList;import java.util.Queue;

public class ShortestPathInBinaryMatrix {

public int shortestPathBinaryMatrix(int[][] grid) {        int n = grid.length;        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {            return -1; // 起点或终点不可达        }        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 pathLength = 1;        while (!queue.isEmpty()) {            int size = queue.size();            for (int i = 0; i < size; i++) {                int[] curr = queue.poll();                int row = curr[0], col = curr[1];                if (row == n - 1 && col == n - 1) {                    return pathLength;                }                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; // 未找到路径    }

public static void main(String[] args) {        ShortestPathInBinaryMatrix solver = new ShortestPathInBinaryMatrix();        int[][] grid = {{0, 1, 0}, {0, 0, 0}, {1, 0, 0}};        int shortestPath = solver.shortestPathBinaryMatrix(grid);        System.out.println('最短畅通路径长度: ' + shortestPath);    }}

时间复杂度： O(n^2)，其中 n 是矩阵的边长。在最坏情况下，我们需要访问所有单元格一次。

空间复杂度： O(n^2)，主要用于存储队列和访问标记数组，空间复杂度与矩阵的大小成正比。