LeetCode 1091. 二进制矩阵中的最短路径

约 7 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 腾讯 字节 华为 快手
标签
数组 广度优先搜索 矩阵

题目描述

✅ 1091. 二进制矩阵中的最短路径

image-20260929000632998

image-20260929000632999

题意分析

在 0 为通路、1 为障碍的方阵中，从左上角走到右下角，可以移动到共享边或角的八个相邻格子。返回最短路径经过的格子总数，起点、终点都计入；无法到达则返回 -1。斜向移动只要求目标格为 0，不要求两侧格子也畅通。

解法：八方向 BFS

核心思路

[!blue]

把每个通路格看作节点，八方向中相邻的通路格之间连边。每次移动都使路径增加一个格子，所以用 BFS 按路径长度从小到大搜索。队列保存 (row, col, distance)，其中 distance 是从起点走到当前格经过的格子数；起点自身已经占一个格子，初始值为 1。

从距离为 distance 的格子扩展邻居时，新距离为 distance+1，并把邻居放到队尾。先进先出的顺序保证出队距离不会变小；若某个格子存在更短路径，它应当已经由更早出队的前驱发现，因此首次入队时的距离就是最短距离，无需再次搜索同一格。

为防止一个格子被不同前驱重复加入，发现它时立即把 grid 中的 0 改成 1。之后，原有障碍与已访问格都统一跳过；这个实现会修改输入网格，但不需要另建访问数组。检查邻居时先判断坐标是否越界，再读取网格值。

起点或终点是障碍时直接无解。其余情况下，终点首次出队便返回距离；n = 1 且唯一格子为 0 时，起点就是终点，会返回 1。若队列耗尽仍未到达终点，说明所有可达通路格都已检查，返回 -1。

解题步骤

  1. 检查起点和终点，任意一个为障碍便返回 -1。
  2. 把 (0, 0, 1) 入队，并把起点标成已访问。
  3. 取出队首；若它是终点，返回保存的 distance。
  4. 枚举八个邻居，跳过越界、障碍和已访问格；其余格子先标记，再以 distance+1 入队。
  5. 队列耗尽仍未找到终点，返回 -1。

代码实现

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[] dr = {
            -1,
            -1,
            -1,
            0,
            0,
            1,
            1,
            1
        };
        int[] dc = {
            -1,
            0,
            1,
            -1,
            1,
            -1,
            0,
            1
        };
        Queue<int[]> queue = new ArrayDeque<>();

        // 路径按格子数计算，起点距离为一
        queue.offer(new int[] {
            0,
            0,
            1
        });
        grid[0][0] = 1;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            int distance = current[2];

            // 队列距离不下降，终点首次出队即可返回最短距离
            if (row == n - 1 && col == n - 1) {
                return distance;
            }

            for (int direction = 0; direction < 8; direction++) {
                int nextRow = row + dr[direction];
                int nextCol = col + dc[direction];

                if (nextRow < 0
                        || nextRow >= n
                        || nextCol < 0
                        || nextCol >= n
                        || grid[nextRow][nextCol] == 1) {
                    continue;
                }

                // 发现时立即标记，同一格子不被多个前驱重复加入
                grid[nextRow][nextCol] = 1;
                queue.offer(new int[] {
                    nextRow,
                    nextCol,
                    distance + 1
                });
            }
        }

        return -1;
    }
}

func shortestPathBinaryMatrix(grid [][]int) int {
    n := len(grid)
    if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
        return -1
    }

    type node struct {
        row, col, distance int
    }
    directions := [8][2]int{
        {-1, -1},
        {-1, 0},
        {-1, 1},
        {0, -1},
        {0, 1},
        {1, -1},
        {1, 0},
        {1, 1},
    }
    // 路径按格子数计算，起点距离为一
    queue := []node{
        {row: 0, col: 0, distance: 1},
    }
    grid[0][0] = 1

    for head := 0; head < len(queue); head++ {
        current := queue[head]
        // 队列距离不下降，终点首次出队即可返回最短距离
        if current.row == n-1 && current.col == n-1 {
            return current.distance
        }

        for _, direction := range directions {
            nextRow := current.row + direction[0]
            nextCol := current.col + direction[1]
            if nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n ||
                grid[nextRow][nextCol] == 1 {
                continue
            }
            // 发现时立即标记，同一格子不被多个前驱重复加入
            grid[nextRow][nextCol] = 1
            queue = append(queue, node{
                row: nextRow, col: nextCol, distance: current.distance + 1,
            })
        }
    }
    return -1
}

复杂度分析

  • 时间复杂度：$O(n^2)$，n 为方阵边长，每格至多入队一次，每次只检查固定的八个方向。
  • 空间复杂度：$O(n^2)$，队列最多保存与网格总格数同阶的状态，访问标记复用输入网格。

关键点总结

[!green]

  • 距离按格子而非边数统计。
  • 先标记再入队，保持一格只展开一次。

易错点总结

[!yellow]

  • 只走四方向会漏掉对角线最短路径。
  • 从零开始计距离，所有合法结果少一。
  • DFS 第一条可行路径不一定最短。

相似题目

题目 难度 关联与区别
1926. 迷宫中离入口最近的出口 中等 同样网格BFS，原题四方向找任意边界出口，本题八方向抵达固定终点且路径长度计格子数。
1293. 网格中的最短路径 困难 原题允许消除一定数量障碍，需要在位置外保存剩余资源，本题只走已有空格。
127. 单词接龙 困难 把合法状态及一次操作建成无权图进行 BFS；本题按可通行的相邻单元扩展路径，该题相差一个字符的单词之间连边。
752. 打开转盘锁 中等 把合法状态及一次操作建成无权图进行 BFS；本题按可通行的相邻单元扩展路径，该题按转动一位数字扩展状态。
773. 滑动谜题 困难 把合法状态及一次操作建成无权图进行 BFS；本题按可通行的相邻单元扩展路径，该题按空位交换扩展棋盘状态。
补充题 131. 四方向网格最短路径的构造 中等 都用 BFS 按层搜索最短路；补充题改为四方向并记录前驱以还原路径。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/82084472
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！