LeetCode LCR 107. 01 矩阵
目录
题目描述
题意分析
给一个只含 0 和 1 的
m × n矩阵，对每一个格子求出它到最近的 0 的距离，距离按四方向相邻计算（即曼哈顿意义下的网格步数）。返回一个同样大小的矩阵。要点在「每一个」和「最近」这两个词上。它不是问某一个点到某一个点的距离，而是所有点到「最近的某一个 0」的距离，本质上是一个多源最短路问题：把所有 0 看成同一个源点集合，求全图到这个集合的距离场。
边权全都是 1，这是最关键的算法信号。边权一致的最短路 = BFS，不需要 Dijkstra，也不需要优先队列。识别出这一点，整道题就只剩实现细节。
约束里
m * n ≤ 10^4，并且题目保证矩阵中至少有一个 0。后者很重要：它保证了每个格子都有解，不会出现「无法到达」的情形，省掉了对-1之类不可达值的处理。「距离场」的语义还带来一条隐含性质：0 所在格子的答案恒为 0，1 所在格子的答案至少为 1。这可以当作写完代码后的自检。
边界：矩阵可能只有一行或一列，越界判断必须四边都写全；矩阵可能全是 0，此时答案就是原矩阵；1 的连片区域可能很大，距离最大能到 $m + n$ 量级，用
int存绰绰有余。
解法：动态规划递推
核心思路
最直接的想法是对每个 1 单独做一次搜索找最近的 0，或者干脆对每个 1 枚举所有 0 取最小曼哈顿距离。前者是 $mn$ 次 BFS，后者是 $O((mn)^2)$ 的两两配对，在 $10^4$ 个格子的规模下都要退化到 $10^8$ 量级。
瓶颈在于把「多个源」当成了「多次单源」来做，同一片区域被反复扫过。而这些搜索之间高度重叠：一个格子只关心离它最近的那个 0，其余 0 的搜索对它是纯粹的浪费。
反过来想：与其从每个 1 出发去找 0，不如从所有 0 同时出发向外扩散。把全部 0 一次性放进队列作为第 0 层，然后一层一层地向外推进，某个格子第一次被触达时所处的层号，就是它到最近 0 的距离。这就是多源 BFS——它和单源 BFS 的唯一区别只是初始队列里有多个起点。
正确性来自 BFS 的层序性质。不变量是：队列中的元素按距离非递减排列，且任何格子被第一次赋值时得到的就是它的最终答案。因为所有源点同时以速度 1 向外扩散，最先碰到某个格子的那条波前，一定来自离它最近的那个 0。
于是状态就是答案矩阵本身：
answer[i][j]表示(i,j)到最近 0 的距离，同时兼作「是否已被访问」的标记。初始化时把它全部填成-1表示未访问，再把所有 0 的位置置 0 并入队。转移：从队列取出
(x, y)，对四个方向的邻居(nx, ny)，若answer[nx][ny] == -1（尚未被任何波前触达），则赋值answer[x][y] + 1并入队。用-1而不是另开一个visited数组，是因为「已赋值」与「已访问」在这道题里是同一件事，一个矩阵同时承担两种语义可以省掉一半空间。队列清空时，每个格子都已被赋值，直接返回答案矩阵。
解题步骤
- 新建与输入同规模的
answer矩阵并整体填-1。为什么用-1而不是 0：0 是合法的距离值（0 所在的格子），拿它当「未访问」标记会与真实答案混淆；-1不可能是任何格子的答案，天然可区分。- 扫描整个矩阵，把每个值为 0 的位置的
answer置 0 并全部入队。为什么要一次性全放进去：这是多源 BFS 的核心，只有让所有源点同处第 0 层，后续的层号才等于「到最近源点的距离」。若只放一个 0 再逐个跑，就退化成多次单源搜索。- 准备方向数组
{-1, 0, 1, 0, -1}。为什么这么写：相邻两项构成一组偏移，滑动取出(-1,0)、(0,1)、(1,0)、(0,-1)恰好四方向，比四段if更短且不会误引入对角线。- 循环出队直到队列为空。为什么用队列而不是栈：队列的先进先出保证了扩散按层推进；换成栈就变成 DFS，第一次触达不再是最短距离，答案会偏大。
- 对每个邻居，先判越界，再判
answer[nx][ny] == -1，成立则赋answer[x][y] + 1并入队。为什么两个判断缺一不可：越界判断防止下标非法，未访问判断保证每个格子只被赋值一次——已经有值说明它被更早（也就是更近）的波前触达过，再改只会变大。- 必须在入队的同时完成赋值，而不是等出队时再赋。为什么：若只入队不标记，同一个格子会被四个邻居重复推入队列，队列规模膨胀，还可能被后到的、更长的路径覆盖。赋值即标记，是 BFS 去重的标准做法。
- 返回
answer。为什么不需要额外检查：题目保证至少存在一个 0，所以初始队列非空、扩散能覆盖全图，不会有格子停留在-1。以
mat = [[0,0,0],[0,1,0],[1,1,1]]走一遍。初始化后
answer全为-1。扫描发现 0 的位置有(0,0)、(0,1)、(0,2)、(1,0)、(1,2)，把它们的answer置 0 并按行优先顺序入队。此时answer是[[0,0,0],[0,-1,0],[-1,-1,-1]]，队列里是这五个源点，构成第 0 层。出队
(0,0)：上方越界、左方越界；右邻(0,1)的值是 0 不是-1，跳过；下邻(1,0)同理跳过。没有新增。出队
(0,1)：下邻(1,1)是-1，赋值answer[0][1] + 1 = 1并入队。其余邻居都已有值。出队
(0,2)：下邻(1,2)已是 0，跳过。出队
(1,0)：下邻(2,0)是-1，赋值0 + 1 = 1并入队；右邻(1,1)此刻已经是 1，跳过——这里正体现了「先到先得」，(1,1)保留了来自(0,1)的更早赋值。出队
(1,2)：下邻(2,2)是-1，赋值 1 并入队。第 0 层耗尽，队列里剩下
(1,1)、(2,0)、(2,2)，都是距离 1 的格子，构成第 1 层。出队
(1,1)：下邻(2,1)是-1，赋值answer[1][1] + 1 = 2并入队。出队
(2,0)：右邻(2,1)此刻已是 2，跳过；上邻已有值。出队
(2,2)：左邻(2,1)已有值，跳过。出队
(2,1)：四邻全部有值，无新增。队列清空。最终
answer = [[0,0,0],[0,1,0],[1,2,1]]。可以验证(2,1)到最近的 0（(1,0)或(1,2)）确实要走两步，而它的两个横向邻居只需一步，与「层号即距离」完全吻合。如果把队列换成栈，
(2,1)可能先沿着(1,1) → (2,1)之外的更长路径被触达，得到 3 而不是 2，答案就错了——这是理解 BFS 为什么必须用队列的最直观反例。
代码实现
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, 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 中每个格子最多入队一次、出队一次，出队时检查常数个（4 个）邻居，总操作量与格子数成正比。
- 空间复杂度：$O(mn)$。凭什么：答案矩阵本身是 $O(mn)$ 且必须返回；队列在最坏情况（矩阵全是 0）下会一次性装下所有格子，同样是 $O(mn)$。没有使用额外的
visited数组，因为答案矩阵已兼任访问标记。
关键点总结
- 「所有点到最近的某类点的距离」是多源 BFS 的标准信号，做法是把所有源点一次性放进初始队列，而不是对每个源跑一次单源 BFS——这个转换能把 $O((mn)^2)$ 直接降到 $O(mn)$。
- 边权全为 1 时 BFS 就是最短路，无需 Dijkstra；能当场说清「什么时候 BFS 够用、什么时候必须上优先队列」，是这类题的核心考点。
- BFS 必须在入队时打标记而不是出队时，否则同一格子会被多次入队，既膨胀队列又可能被更长的路径覆盖。
- 用答案矩阵的哨兵值（这里是
-1）兼作访问标记，可以省掉一整个visited数组；前提是哨兵值不可能是任何合法答案。- 方向数组的滑动窗口写法
{-1,0,1,0,-1}是网格题的通用模板，四方向、八方向只需换一组常量，比堆叠if更不容易漏分支。- 面试视角：本题还有一个 $O(mn)$ 的两遍 DP 解法（先左上到右下、再右下到左上各扫一次，取邻居最小值加一）。能同时给出 BFS 与 DP 两条路，并说明 DP 版常数更小但只适用于曼哈顿距离场，会明显加分。
易错点总结
- 只把一个 0 入队而不是全部：
mat = [[0,1],[1,0]]中若只放(0,0)，(1,1)会被算成 2，而正确答案是 1。- 用 0 当「未访问」标记：
mat = [[0,0],[0,0]]中所有格子的正确答案都是 0，却会被当成未访问反复入队，队列永不清空导致死循环。- 出队时才打标记：
mat = [[0,1,1]]中(0,1)会被(0,0)和(0,2)的探测重复入队，规模较大时队列膨胀到 $O(mn)$ 倍，超时甚至内存溢出。- 把队列换成栈（写成 DFS）：
mat = [[0,0,0],[0,1,0],[1,1,1]]中(2,1)可能沿更长路径先被触达而得到 3，正确答案是 2。- 越界判断漏写某一侧：只写
x < m && y < n而漏掉非负判断，mat = [[0]]在向上探测时访问answer[-1][0]，Java 抛越界异常、Go panic。- 赋值时写成
answer[x][y] = answer[x][y] + 1：mat = [[0,1]]中(0,1)的初值是-1，会被赋成 0，与「1 的格子距离至少为 1」矛盾；正确的来源是当前出队格子的距离。- 先入队再赋值，且赋值依赖出队时读取：
mat = [[0,1,1],[1,1,1]]中同一格子被多个邻居推入，后续出队时读到的父格距离不再是最小的，部分格子的结果偏大。- 直接在
mat上原地改写距离：mat = [[0,1,1]]中把(0,1)改成 1 后，判断(0,2)时无法再区分「原本是 1」和「已被赋距离 1」，逻辑彻底混乱。- 担心矩阵全是 1 而加不可达处理：题目已保证至少有一个 0，多写的分支不会被触发，只会让白板代码变长。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 542. 01 矩阵 | 中等 | 与本题同题，可直接套用同一份代码 |
| 994. 腐烂的橘子 | 中等 | 同为多源 BFS，但要按层计数并在结束后检查是否还有新鲜橘子残留 |
| 1162. 地图分析 | 中等 | 多源 BFS 求的是距离场的最大值，且需处理全陆地或全海洋返回 -1 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 单源单终点，八方向连通，起点终点被堵时要提前判否 |
| 127. 单词接龙 | 困难 | 状态是字符串而非坐标，邻居靠逐位换字母现场生成，需要哈希集合去重 |
| 752. 打开转盘锁 | 中等 | 状态图是隐式的，还多了「死亡数字」这类被禁止的节点 |
| 909. 蛇梯棋 | 中等 | 需要把蛇形编号映射回二维坐标，且一步的邻居是骰子的六个结果 |
| 1345. 跳跃游戏 IV | 困难 | 同值下标之间互为邻居，必须在用过一次后清空该值的列表以免退化成平方 |
| LCR 108. 单词接龙 | 困难 | 与 127 同题，可用来对照坐标状态与字符串状态在实现上的差异 |