题目描述
思路解析动画文字版
看一眼这个矩阵：这是我们的例子：左上角连着三个 0（蓝色），其余都是 1（绿色）。目标是把每个 1 替换成「它离最近 0 有多远」。
先想最直白的办法：最直白的想法：对每一个 1，单独做一次广度优先搜索，从它出发往外扩，第一次碰到 0 时走过的步数就是答案。
笨办法 · 给一个 1 找 0：比如右下角 (2,2) 这个 1（紫色）。把它当起点，向四周扩散，一圈圈搜，直到撞上一个 0 才停。
笨办法 · 扩了第 1 圈：从 (2,2) 往外扩第 1 圈，碰到 (1,2)、(2,1)（紫色），它们都还是 1，没撞到 0，得接着往外扩。
笨办法 · 扩了好几圈才碰到 0：为了搞清楚这一个格子的答案，它要往外扩好几圈才碰到 0。每个 1 都这样来一遍，重复搜索的格子太多，太慢了。
为什么慢：假设有 m×n 个 1，每个都从头搜一遍整张图，这就是平方级的重复劳动。格子稍多就会超时。我们需要换个思路。
关键反转：反转一下：与其让每个 1 去找 0，不如让所有的 0 一起向外扩散。第一波碰到的 1 距离是 1，第二波是 2……谁先被碰到，谁的答案就先定下来。
为什么从 0 出发是对的：广度优先搜索天然按距离一层层往外走：距离 1 的全走完，才走距离 2 的。所以一个格子第一次被碰到时记下的步数，一定就是它离最近 0 的最短距离，之后不用再改。
第 0 层 · 把第 1 个 0 入队：开局把所有 0 入队、距离记 0。先看第一个 0 —— (0,0)，距离 0（紫色），放进队列。其余还没确定的格子先标成「·」。
第 0 层 · 第 2 个 0 入队：第二个 0 是 (0,1)，距离也是 0，一并入队。看队列又多了一个 d=0。
第 0 层 · 第 3 个 0 入队：最后一个 0 是 (1,0)，距离 0 入队。现在三个 0 全在队列里（距离都 0），这就是多源 BFS的「多源」——同时从它们起跑。
第 1 层 · 扩出 (0,2)：把第 0 层的 0 依次取出看邻居。(0,1) 右边的 (0,2) 第一次被碰到，距离 = 0 + 1 = 1（紫色波面），填进格子并入队。三个 0 变蓝表示已处理。
第 1 层 · 扩出 (1,1)：中间的 (1,1) 被它上面的 0、左边的 0 一步碰到，距离记 1。(0,2) 这格答案已锁定变蓝。波面一格一格往里填。
第 1 层 · 扩出 (2,0)：(1,0) 下面的 (2,0) 也第一次被碰到，距离 1。至此距离 1 的一整圈都填好了：(0,2)、(1,1)、(2,0)，它们排队等下一轮往外扩。
第 1 层 · 距离填好：距离 1 的三个格子全部锁定（蓝色=已确定），不会再改。每个 1 都是被离它最近的那个 0 一步碰到的——这正是多源同时扩散的好处。
第 2 层 · 扩出 (1,2)：现在轮到距离 1 的那一圈往外扩。(1,2) 被 (0,2) 或 (1,1) 碰到，第一次到达，距离 = 1 + 1 = 2（紫色波面），填上并入队。
第 2 层 · 扩出 (2,1)：(2,1) 被 (1,1) 或 (2,0) 碰到，距离也是 2。(1,2) 锁定变蓝。距离 2 的这圈填完了，只剩最角落的 (2,2) 还是「·」。
第 2 层 · 距离填好：(1,2) 和 (2,1) 的距离锁定为 2。波面一圈圈往外推，只剩最角落的 (2,2) 还没确定。
第 3 层 · 扩到最角落 (2,2)：距离 2 的格子往外扩，碰到最后的 (2,2)。它第一次被碰到，距离 = 2 + 1 = 3（紫色波面），填上。
全部确定 · 完成：队列空了，所有格子的距离都确定了：[[0,0,1],[0,1,2],[1,2,3]]。整张图只扫了一遍，每个格子只在第一次被碰到时写一次值。
回看波面 · 距离 1 那一圈：回看这道波是怎么漫开的。紫色高亮的是距离 1那一圈：(0,2)、(1,1)、(2,0)，紧贴着那片 0。
回看波面 · 距离 2 那一圈：再外一圈是距离 2：(1,2)、(2,1)。它们离那片 0 隔了一圈，所以是两步。
回看波面 · 距离 3 最外圈：最外圈只有最角落的 (2,2)，距离 3。整张图就是从左上那片 0 出发，像水波一样一圈圈漫开：1、2、3。每个格子的数字 = 这道波第几圈漫到它。
提速对比：从「每个 1 单独搜全图」变成「所有 0 一起扩散、全图只走一遍」，复杂度从平方级降到线性级，这就是多源 BFS 的威力。
落到代码 · 三步走：用 -1 标记「还没访问」非常好用：邻居只要还是 -1，就说明它第一次被碰到，写上距离并入队；已经不是 -1 的就跳过，绝不重复。
本质金句：多源 BFS 的本质：把所有起点想象成连到一个「超级源点」，从它出发的一次普通 BFS，就同时算出了到「最近任意一个起点」的距离。
易错实演 · 方向反了：如果坚持从每个 1（红色）出发各搜一遍，(1,1)、(1,2)、(2,2) 的搜索范围会大量重叠，同一片区域被反复走，这就是慢的根源。
边界三连：题目保证至少有一个 0，所以不会出现「找不到 0」的死局。全 0、单 0、单格这些极端情况，多源 BFS 模板都能自然兜住。
面试追问：面试时常被追问「为什么是 BFS 不是 DFS」和「有没有 DP 解法」，把这两点讲清楚能体现你对最短路本质的理解。
参考代码
from collections import dequeclass Solution: def updateMatrix(self, mat): m, n = len(mat), len(mat[0]) dist = [[-1] * n for _ in range(m)] q = deque() for i in range(m): for j in range(n): if mat[i][j] == 0: dist[i][j] = 0 q.append((i, j)) dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: i, j = q.popleft() for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n and dist[ni][nj] == -1: dist[ni][nj] = dist[i][j] + 1 q.append((ni, nj)) return dist复杂度
- 时间：O(m·n)，每个格子只入队、出队一次，整张图只扫一遍
- 空间：O(m·n)，距离矩阵 + 队列，最坏一半格子同时在队里
易错点
面试追问把动画讲成自己的话
追问为什么不用 DFS 做这题？
追问能不能不用 BFS，用动态规划？
追问如果距离按八个方向（含对角线）算呢？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
腐烂的橘子
LeetCode 994 · 中等 · 沿着 多源套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题