LeetCode 542. 01 矩阵

2026-04-15 HGNULB 约 10 分钟

文章信息 7 个分类 7 个标签

分类

题目描述

✅ 542. 01 矩阵

题意分析

给定一个只含 0 和 1 的矩阵，要求为每个格子算出它到最近的 0 的距离，距离按上下左右四方向相邻计一步。输出是一个同样大小的矩阵。

值得注意的是「最近的 0」并不指定是哪一个 0，也就是说每个 1 的答案由离它最近的那个 0 决定，而不同的 1 可以对应不同的 0。这提示答案不是围绕单个源点展开的。

约束里保证矩阵中至少有一个 0，所以不存在无解格子，不需要处理无穷大的输出。矩阵规模可达一万行一万列量级、但总格数有限，说明允许的总代价大致是把每个格子处理常数次。

边界情况有两类：格子本身是 0 时答案为 0；整个矩阵全是 0 时输出与输入同形且全零。另外要留意 1 的数量可能远多于 0，也可能远少于 0，解法不该对这两种分布有偏好。

解法：多源 BFS

核心思路

直觉解法是对每个值为 1 的格子单独做一次广度优先搜索，一路扩散直到碰到第一个 0。结果正确，但代价是「1 的个数」乘以「一次搜索的代价」，在几乎全是 1 的矩阵上会退化成格子数的平方级别。

瓶颈在于同一片区域被反复扫描：相邻的两个 1 走的扩散路径高度重合，却各算各的。反过来想，如果把搜索的方向倒过来——不是从 1 出发找 0，而是从所有 0 出发向外扩散——那么每个 0 的影响范围会自然拼接，整张图只需要扫一遍。

把所有 0 同时放进队列作为第 0 层，等价于在原图外面虚拟一个超级源点，它到每个 0 的边权为 0，再从这个超级源点做一次普通的广度优先搜索。由于每条边的权重都是 1，广度优先搜索按层扩散的性质保证了：一个格子第一次被弹出的时刻所记录的距离，就是它到最近 0 的最短距离，此后不会再被更短的路径改写。这就是本题的不变量。

具体到实现，用距离矩阵本身兼作访问标记：0 的位置初始化为 0，1 的位置初始化为 -1 表示未确定。这样就不需要额外的 visited 数组，判断「是否已定值」和「取距离」是同一次读取。

解题步骤

扫一遍矩阵，把所有 0 的坐标入队并把距离置 0，把 1 的距离置 -1。之所以要一次性全部入队，是因为这些 0 共同构成搜索的第 0 层，只有同时出发才能保证扩散的波前是按真实距离推进的。

用两个整型数组加头尾下标模拟队列。总入队次数不会超过格子总数，所以定长数组足够，省掉了链式队列的分配开销。

循环从队头取出坐标，用方向数组 {-1, 0, 1, 0, -1} 的相邻两项组成四个方向的偏移。这种写法比写四个 if 更短，也不容易漏方向。

对每个邻居先做越界判断，再看它的距离是否仍是 -1。只有仍是 -1 才更新为当前距离加一并入队；已经有值说明它在更早或同一层就被确定过，那个值只会更小或相等。

关键在于「赋值即入队」：更新距离的同时立刻入队，等价于在入队时刻就完成了访问标记。若把标记推迟到出队，同一个格子会被多个邻居重复推进队列。

队列排空后距离矩阵即为答案，直接返回，不需要额外一轮转换。

以 mat = [[0,0,0],[0,1,0],[1,1,1]] 走一遍：初始化后 dist 为 [[0,0,0],[0,-1,0],[-1,-1,-1]]，队列依次装入 (0,0)、(0,1)、(0,2)、(1,0)、(1,2) 这五个 0。

弹出 (0,0)，四个邻居中 (1,0) 和 (0,1) 的距离都不是 -1，无事发生。弹出 (0,1)，下方 (1,1) 距离为 -1，置为 $0 + 1 = 1$ 并入队。弹出 (0,2)，下方 (1,2) 已是 0，跳过。弹出 (1,0)，下方 (2,0) 为 -1，置为 $0 + 1 = 1$ 并入队；右方 (1,1) 此刻已是 1，跳过。弹出 (1,2)，下方 (2,2) 为 -1，置为 1 并入队。

第一层处理完，队列里是 (1,1)、(2,0)、(2,2)，距离都是 1。弹出 (1,1)，下方 (2,1) 为 -1，置为 $1 + 1 = 2$ 并入队。弹出 (2,0)，右方 (2,1) 已是 2，跳过。弹出 (2,2)，左方 (2,1) 同样跳过。最后弹出 (2,1)，四周再无 -1。

队列排空，dist 为 [[0,0,0],[0,1,0],[1,2,1]]。注意 (2,1) 的答案 2 来自 (1,1) 这条路径，而 (2,0) 的答案 1 来自另一个 0，这正是多源扩散相对单源搜索的价值所在。

代码实现

class Solution {
    // 如果从每个 1 分别 BFS，复杂度会乘以 1 的数量，双重遍历很重。
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];
        int[] qx = new int[m * n];
        int[] qy = new int[m * n];
        int head = 0;
        int tail = 0;
        int[] dirs = new int[] {-1, 0, 1, 0, -1};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    qx[tail] = i;
                    qy[tail] = j;
                    tail++;
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = -1;
                }
            }
        }

        while (head < tail) {
            int x = qx[head];
            int y = qy[head];
            head++;
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d];
                int ny = y + dirs[d + 1];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n || dist[nx][ny] != -1) {
                    continue;
                }
                dist[nx][ny] = dist[x][y] + 1;
                qx[tail] = nx;
                qy[tail] = ny;
                tail++;
            }
        }
        return dist;
    }
}

func updateMatrix(mat [][]int) [][]int {
    // 如果从每个 1 分别 BFS，复杂度会乘以 1 的数量，双重遍历很重。
    m := len(mat)
    n := len(mat[0])
    dist := make([][]int, m)
    qx := make([]int, m*n)
    qy := make([]int, m*n)
    head, tail := 0, 0
    dirs := []int{-1, 0, 1, 0, -1}

    for i := 0; i < m; i++ {
        dist[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if mat[i][j] == 0 {
                dist[i][j] = 0
                qx[tail] = i
                qy[tail] = j
                tail++
            } else {
                dist[i][j] = -1
            }
        }
    }

    for head < tail {
        x := qx[head]
        y := qy[head]
        head++
        for d := 0; d < 4; d++ {
            nx := x + dirs[d]
            ny := y + dirs[d+1]
            if nx < 0 || ny < 0 || nx >= m || ny >= n {
                continue
            }
            if dist[nx][ny] != -1 {
                continue
            }
            dist[nx][ny] = dist[x][y] + 1
            qx[tail] = nx
            qy[tail] = ny
            tail++
        }
    }
    return dist
}

复杂度分析

时间复杂度：$O(m \cdot n)$，每个格子只在距离从 -1 变为确定值的那一刻入队一次，出队后固定检查 4 个方向，所以总操作量是格子数的常数倍，与 0 和 1 的分布无关。

空间复杂度：$O(m \cdot n)$，距离矩阵是必须的输出，队列在最坏情况（矩阵全为 0）下会同时容纳所有格子，两者都是格子数量级。

关键点总结

「每个点到最近的某类点的距离」是多源最短路的标准信号，方向应当反转：从所有目标点同时出发，而不是从每个查询点各走一次。

多源广度优先搜索等价于加一个到所有源点边权为 0 的超级源点，理解了这个等价关系，就不必怀疑同时入队是否会破坏层序性质。

边权全为 1 是广度优先搜索能给出最短路的前提。一旦边权不等，就必须换成优先队列，这条界限在面试里经常被追问。

用结果数组的哨兵值（这里是 -1）兼作访问标记，既省一个数组，也让「已确定」和「取值」合并为一次读取，减少状态不一致的可能。

标记时机必须是入队时而非出队时。这是广度优先搜索最常见的效率与正确性分水岭，写多源版本时尤其容易忽略。

面试视角：先说出朴素解法及其复杂度上界，再点明「反向扩散」的观察，最后才写代码。能主动补一句「若把 0 和 1 的角色对调，或者改成八连通，代码只需改初始化和方向数组」，会显著提升评价。

易错点总结

错误写法：对每个值为 1 的格子各做一次广度优先搜索。mat 为 200×200 且只有右下角一个 0 → 近四万个格子各自扩散一遍，总操作量达到十亿量级，直接超时。

错误写法：只把第一个遇到的 0 入队，然后再逐个补。[[0,0,0],[0,1,0],[1,1,1]] → 波前不再按真实距离推进，(2,0) 会先从远处的 0 拿到偏大的值并被锁定，输出 [[0,0,0],[0,1,0],[2,2,1]] 之类的错误结果。

错误写法：把访问标记放在出队时。全 0 矩阵 → 每个格子被四个邻居各推一次，队列长度膨胀到格子数的四倍，预分配的定长队列数组越界。

错误写法：把 1 的初始距离设成 0 而不是 -1。[[0,1]] → 判断「是否已确定」时把真正未访问的格子误当成已确定，(0,1) 永远不会被更新，输出 [[0,0]]。

错误写法：用一个足够大的正数（如 Integer.MAX_VALUE）作未访问标记，更新时写成 dist[nx][ny] = dist[x][y] + 1 却不判断是否已访问。任何含 1 的用例 → 已确定的格子被后来的更长路径覆盖，答案偏大。

错误写法：方向数组写成 {-1, 0, 1, 0} 并按 dirs[d] 与 dirs[d + 1] 取偏移。任意矩阵 → 第四个方向读到下标 4 越界，或用取模绕回后重复了第一个方向而漏掉左方，最左侧的 1 拿不到正确距离。

错误写法：越界判断写在读取 dist[nx][ny] 之后。第 0 行任意格子 → 先访问 dist[-1][y] 就已经抛出下标异常。

错误写法：假设矩阵是方阵，用同一个边长同时判断行和列。[[0,0,0,0,1]] 这类扁平矩阵 → 列方向的合法下标被误判为越界，右侧的 1 保持 -1 不变。

错误写法：入队后忘记推进队尾下标，或出队后忘记推进队头下标。任意含 1 的用例 → 前者让新格子被后续写入覆盖导致漏搜，后者让循环永远处理同一个坐标而死循环。

相似题目

题目	难度	考察点
994. 腐烂的橘子	中等	同为多源扩散，但要的是总层数并判断是否有剩余
1162. 地图分析	中等	多源扩散后取所有距离的最大值
1091. 二进制矩阵中的最短路径	中等	单源八连通网格，答案是经过的格子数
1293. 网格中的最短路径	困难	状态要附加剩余消除次数，访问标记升到三维
909. 蛇梯棋	中等	棋盘一维化并处理蛇与梯子造成的跳转边
1129. 颜色交替的最短路径	中等	状态要记住上一条边的颜色，同点两份距离
127. 单词接龙	困难	隐式图，邻居靠逐位替换字符临时枚举
433. 最小基因变化	中等	字符集只有四个，可直接暴力枚举全部邻居
752. 打开转盘锁	中等	带禁止状态的转盘图，适合双向搜索
773. 滑动谜题	困难	把棋盘序列化成字符串当作图节点
854. 相似度为 K 的字符串	困难	邻居由交换生成，需剪掉无意义的交换
1345. 跳跃游戏 IV	困难	等值下标之间的超级边用完必须清空
1654. 到家的最少跳跃次数	中等	一维无界坐标，需要先推导搜索范围上界
LCP 09. 最小跳跃次数	困难	单向弹簧图，用已扩散前缀避免重复回退
1298. 你能从盒子里获得的最大糖果数	困难	队列驱动的可达性传播，钥匙与盒子互相解锁
LCR 108. 单词接龙	困难	127 的 LCR 编号，可用来复核模板熟练度
LCR 109. 打开转盘锁	中等	752 的 LCR 编号，注意起点即禁止态的边界