LeetCode 542. 01 矩阵

约 6 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 携程
标签
数组 动态规划 广度优先搜索 矩阵

题目描述

✅ 542. 01 矩阵

image-20260928224313685

image-20260928224313686

题意分析

对每个格子，求沿上下左右移动到任意一个零的最少步数。零到自身的距离是 $0$，题目保证至少有一个零。相邻格子间每次移动都花费一步，适合用 BFS 求最短距离。

解法：多源 BFS

核心思路

[!blue]

从每个位置寻找最近零，会重复搜索大量格子。由于相邻格子可以双向移动，可以反过来让所有零同时向外扩展：某格最先被哪个零到达，就得到到最近零的距离。

先把全部零设为距离 $0$ 并加入同一个队列，其余格子设为 -1，表示尚未确定。BFS 按距离从小到大处理节点；从距离为 $d$ 的格子发现未访问邻居时，将其距离写为 $d+1$，再入队。

第一次发现就是最短距离：如果该邻居还存在更短路线，那么这条路线的前一个格子距离更小，早已出队并发现它，不可能到现在仍未访问。因此距离写入后无需再次更新，也无需区分它来自哪个零。

距离表同时充当访问标记，入队前就赋值，防止多个来源重复加入同一格。每格最多入队一次，所以两份同步保存行、列的队列只需预分配 $mn$ 个位置。题目没有不可通行的格子，且至少有一个零，搜索结束后所有距离都会确定。

解题步骤

  1. 完整遍历矩阵：零的距离设为 $0$ 并入队，一的距离设为 -1。
  2. 取出队头坐标，枚举四个相邻位置。
  3. 跳过越界或距离不为 -1 的邻居；其余邻居首次被发现，赋值为当前距离加一后入队。
  4. 队列耗尽后返回距离矩阵。若全部格子都是零，每格已在初始化时得到答案，搜索不会修改这些距离。

代码实现

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(mn)$，初始化扫描全部格子，搜索中每格最多出队一次并检查四个邻居。
  • 空间复杂度：$O(mn)$，队列预分配格子总数大小，另有输出距离矩阵。

关键点总结

[!green]

  • 所有零必须在向外扩展前完成初始化。
  • 距离确定于入队时，而不是等待出队后才标记。
  • 两份坐标队列同步读写，每格最多入队一次，所以容量 mn 足够。

易错点总结

[!yellow]

  • 只从一个零开始，会把到其他零更近的位置算远。
  • 未处理的一也初始化为零，会与已确定位置混淆。
  • 读取邻居前不检查行列范围，会在边缘越界。

相似题目

题目 难度 关联与区别
994. 腐烂的橘子 中等 同样多源BFS，让所有初始源同时入队，层数表示到最近源的距离。
1162. 地图分析 中等 同样从所有陆地或目标格同时扩展，原题取各格最近距离中的最大值，本题返回完整距离矩阵。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/leetcode-542
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！