LeetCode LCR 107. 01 矩阵

约 6 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 动态规划 广度优先搜索 LCR 矩阵

题目描述

✅ LCR 107. 01 矩阵

image-20260929004510496

image-20260929004510497

题意分析

对矩阵中的每个格子，求它到最近零格的四方向距离，每走到一个相邻格子计一步。零格自身距离为零，题目保证至少存在一个零。

所有格子都可以经过，每次移动的代价相同。与其从每个格子分别寻找零，不如让全部零同时向外搜索，一次得到所有格子到最近源点的最短距离。

解法：多源 BFS 求最近零距离

核心思路

[!blue]

建立答案矩阵 answer，先用 -1 表示尚未确定距离，再把所有零格的答案设为 0 并加入同一个队列。它们共同构成 BFS 的第零层，不需要先为每个普通格子指定它属于哪个零。

队列按距离非递减的顺序处理。取出一个距离为 d 的格子后，检查四个邻居；合法且尚未访问的邻居可经当前格子到达零，因此将它的距离设为 d+1 并入队。

首次赋值就是最短距离：如果该邻居存在更短路径，那么那条路径上距离更小的前一个格子应当更早出队，并已为它赋值，与当前仍为 -1 矛盾。由于所有零同时从距离零开始，这个论证比较的是所有源点的路径，得到的正是最近零距离。

赋值同时承担访问标记，必须在入队时完成，防止其他邻居再次把同一个格子加入队列。之后已有距离的格子无需更新，每个格子最多入队一次。

整个矩形网格连通，且至少有一个源点，所以队列耗尽时所有格子都已有答案。原矩阵只用于确定源点，距离和访问状态统一保存在新矩阵中。

解题步骤

  1. 创建同样大小的答案矩阵，全部填成 -1。
  2. 扫描输入，将所有零格的答案设为零，并全部放入初始队列。
  3. 不断取出队首，使用方向数组检查上下左右四个邻居。
  4. 邻居未越界且答案仍为 -1 时，设为当前格距离加一，再加入队尾。
  5. 队列为空后返回答案矩阵。单行、单列和全零矩阵都由同一流程处理。

代码实现

class Solution {

    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] answer = new int[m][n];

        // -1 表示尚未被任何波前触达，与合法距离 0 区分开。
        for (int i = 0; i < m; ++i) {
            Arrays.fill(answer[i], -1);
        }

        Deque<int[]> q = new LinkedList<>();

        // 所有 0 同时作为第 0 层入队，这是多源 BFS 的关键。
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 0) {
                    answer[i][j] = 0;
                    q.offer(new int[] {
                        i,
                        j
                    });
                }
            }
        }

        int[] dirs = new int[] {
            -1,
            0,
            1,
            0,
            -1
        };

        while (!q.isEmpty()) {
            int[] t = q.poll();

            for (int i = 0; i < 4; ++i) {
                int x = t[0] + dirs[i];
                int y = t[1] + dirs[i + 1];

                // 赋值即标记：第一次被触达时得到的就是最短距离。
                if (x >= 0 && x < m && y >= 0 && y < n && answer[x][y] == -1) {
                    answer[x][y] = answer[t[0]][t[1]] + 1;
                    q.offer(new int[] {
                        x,
                        y
                    });
                }
            }
        }

        return answer;
    }
}

func updateMatrix(mat [][]int) [][]int {
    m, n := len(mat), len(mat[0])
    answer := make([][]int, m)
    // -1 表示尚未被任何波前触达，与合法距离 0 区分开。
    for i := range answer {
        answer[i] = make([]int, n)
        for j := range answer[i] {
            answer[i][j] = -1
        }
    }
    type pair struct{ x, y int }
    var q []pair
    // 所有 0 同时作为第 0 层入队，这是多源 BFS 的关键。
    for i, row := range mat {
        for j, v := range row {
            if v == 0 {
                answer[i][j] = 0
                q = append(q, pair{i, j})
            }
        }
    }
    dirs := []int{
        -1,
        0,
        1,
        0,
        -1,
    }
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        for i := 0; i < 4; i++ {
            x, y := p.x+dirs[i], p.y+dirs[i+1]
            // 赋值即标记：第一次被触达时得到的就是最短距离。
            if x >= 0 && x < m && y >= 0 && y < n && answer[x][y] == -1 {
                answer[x][y] = answer[p.x][p.y] + 1
                q = append(q, pair{x, y})
            }
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(mn)$。初始化扫描全图，BFS 中每个格子最多进出队列各一次，并只检查四个方向。
  • 空间复杂度：$O(mn)$。答案矩阵需要线性空间，队列最坏也会同时保存所有格子，例如初始全为零时。

关键点总结

[!green]

  • 多源 BFS 的所有源点必须一起以距离零入队，层序才同时比较到各个零的距离。
  • 首次抵达的路径最短，已经赋值的格子可以直接跳过。
  • -1 与合法距离零不同，可以由答案矩阵兼任访问标记。
  • 当前格距离加一得到邻居距离，入队和赋值应在同一步完成。

易错点总结

[!yellow]

  • 只放一个零作为源点，会求出到这个零的距离，而非到最近零的距离。
  • 用默认的零表示未访问，会与零格的真实答案混淆。
  • 等到出队才标记，同一格子可能被多个邻居重复入队。
  • 使用栈却仍保留首次访问即定值的规则，无法保证第一次找到的路径最短。
  • 给邻居原有的 -1 加一，会得到错误距离；应读取当前出队格子的距离。

相似题目

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