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

2026-04-14 HGNULB 约 6 分钟

文章信息 9 个分类 3 个标签

分类

题目描述

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

题意分析

在一个 n × n 的 0/1 方阵里从左上角走到右下角，0 可以踩、1 是障碍，每一步可以走到相邻的八个格子中的任意一个。要求返回最短路径上经过的格子数，走不通返回 -1。

「格子数」而不是「移动步数」是这题第一个坑。起点自己就算 1，所以 1 × 1 且值为 0 的网格答案是 1 而不是 0，两种口径永远差 1。

八方向移动是第二个信号。斜着走和横竖走的代价完全一样（都是路径上多一个格子），所以这是一张边权全为 1 的无权图，而不是需要 Dijkstra 的带权图。

约束里 n 最大 100，格子总数一万，说明线性遍历整张网格是完全可行的，重点在于别把同一个格子重复展开。

边界情形：起点或终点本身是障碍时直接无解；起点和终点重合（n = 1）时答案是 1；整张网格可能完全被障碍隔断，此时返回 -1。

解法：八方向 BFS

核心思路

把每个可通行格子视为图节点，相邻八个格子之间有一条代价为 1 的边。所有边权相同，BFS 按距离逐层扩展，因此某个格子第一次入队时，到达它的路径已经最短；DFS 找到的第一条路径则没有这个保证。

队列存 (row, col, dist)，其中 dist 是路径经过的格子数，所以起点距离为 1。格子必须在入队时标记访问，防止同层多个前驱重复入队。代码复用 grid 的障碍标记，将访问过的 0 改为 1。

不变量：队列按距离非递减排列，且每个入队格子的 dist 是起点到它的最短距离。因此终点第一次出队时即可返回。

解题步骤

若起点或终点为 1，直接返回 -1。

将起点以距离 1 入队，并立即标记为已访问。

依次取出队首，若是终点就返回其距离。

枚举八个方向；对未越界且值为 0 的邻居，先标记，再以 dist + 1 入队。

队列耗尽仍未到达终点，返回 -1。

对 [[0,0,0],[1,1,0],[1,1,0]]，最短路径可为 (0,0) → (0,1) → (1,2) → (2,2)，经过 4 个格子；这也说明不能漏掉对角线方向。

代码实现

import java.util.ArrayDeque;
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[] 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)$。每个格子最多入队一次，每次固定检查八个方向。

空间复杂度：$O(n^2)$。队列最坏可保存线性数量的格子；访问状态复用输入矩阵。

关键点总结

无权图最短路使用 BFS，第一次到达节点时距离最短。

路径长度按格子数计，起点距离应初始化为 1。

访问标记要在入队时写入，保证每个格子最多入队一次。

原地标记节省 visited 数组，但会修改输入矩阵，面试时应主动说明。

易错点总结

只枚举四个方向：会漏掉合法的对角线最短路。

距离从 0 开始：[[0]] 应返回 1，而不是 0。

出队时才标记访问：同一格子可能被多个前驱重复加入队列。

不检查起点或终点障碍：会从非法起点扩展，或做无意义搜索。

用 DFS 找到一条路径就返回：第一条可行路径不保证最短。

相似题目

题目	难度	考察点
127. 单词接龙	困难	节点是单词，要用通配符建桶压缩边数
433. 最小基因变化	中等	状态空间小，可直接枚举单字符替换生成邻居
542. 01 矩阵	中等	多源 BFS，所有 0 同时入队作为第 0 层
752. 打开转盘锁	中等	隐式图，需先把死亡数字放进访问集合
773. 滑动谜题	困难	把整个棋盘编码成字符串当作图节点
854. 相似度为 K 的字符串	困难	邻居由交换生成，要靠剪枝压住分支因子
909. 蛇梯棋	中等	编号与坐标是蛇形映射，梯子构成额外的跳跃边
994. 腐烂的橘子	中等	多源 BFS 按层计时，还要判断是否有橘子永不腐烂
1129. 颜色交替的最短路径	中等	状态要带上一条边的颜色，等于把每个点拆成两份
1162. 地图分析	中等	多源 BFS 求最大距离，答案落在最后一层
1293. 网格中的最短路径	困难	状态多一维「剩余可消除障碍数」
1298. 你能从盒子里获得的最大糖果数	困难	可达性随钥匙动态解锁，需回扫暂时打不开的盒子
1345. 跳跃游戏 IV	困难	同值下标构成超级边，用过一次必须清空避免重复展开
1654. 到家的最少跳跃次数	中等	状态要带「上一步是否后退」，还得推导坐标上界
LCP 09. 最小跳跃次数	困难	弹簧只能向右弹，靠已访问前缀边界做剪枝
LCR 107. 01 矩阵	中等	542 的换号版，适合复盘多源 BFS 的初始化
LCR 108. 单词接龙	困难	127 的换号版，可用来练双向 BFS 写法
LCR 109. 打开转盘锁	中等	752 的换号版，适合复盘死亡状态的剪枝时机