小时候做题最怕一种情况思路看着理直气壮一提交就被测试用例教做人。我说的就是这道让我错题本上又多了一页的题——编号第69道核心就四个字“0-1矩阵”。说的是给你一个二维矩阵里面只放0和1要求算出每个格子到离它最近的0的距离上下左右相邻的两个格子之间距离记作1。听起来是不是特别朴素我当时也是这么觉得的结果一上来就踩了个大坑不仅超时还让我把“图论里最朴素的BFS”重新认识了一遍。这篇就把我踩坑的过程、两种主流解法、还有那些面试官喜欢埋的边角细节全部拆开写清楚。不管你是刚刷题的萌新还是准备校招实习、打算把经典题彻底吃透这篇应该都能帮你省下不少弯路。1. 错题复盘第69题“0-1矩阵”是怎么让我翻车的1.1 题目原型每个单元格到最近0的距离先把题目通义一下。输入是一个 m 行 n 列的二维数组元素只有 0 和 1。你要输出一个同样大小的矩阵里面每个位置的值表示原矩阵里这个位置到“最近的0”的曼哈顿距离只不过这里只能上下左右走不能斜着走。举个例子输入: [[0, 0, 0], [0, 1, 1], [1, 1, 1]]输出长这样[[0, 0, 0], [0, 1, 1], [1, 2, 2]]因为右下角的 1离最近的 0 要绕两步右 → 上 → 上或者下 → 左 → 上最近距离就是 2。这道题还有一个常见变体LeetCode 上叫“01 Matrix”面试里出现频率不低。主要考察你对广度优先搜索的理解程度以及能不能想出比“暴力BFS”更高效的做法。1.2 我当时为什么写错被“距离”两个字带偏了我第一次看到这题脑子里瞬间跳出来的方案是遍历每一个 1对每个 1 单独做一次 BFS找到第一个遇到的 0距离就出来了。听着没毛病吧每个 1 都去找离它最近的 0不就是题目要求吗问题出在复杂度上。假设矩阵是 100×100里面有 5000 个 1每个 1 都来一次 BFS最坏情况下每次 BFS 要把整个矩阵扫一遍也就是 10000 个格子。总计算量就是 5000 × 10000 5000 万次操作。感觉还行如果把矩阵放大到 1000×10005000 万个 1 那不是理论值是真实可能出现的场景那时候就是 5000 万 × 100 万直接爆炸。所以我的代码在 100×100 的小样例上跑得飞快一到大数据就原地去世。这种“每个点单独搜一次”的思路错就错在忽略了多个目标点的搜索过程有大量重复计算。两个相邻的 1 各自做 BFS访问的重叠区域非常多这些重复劳动完全可以避免。1.3 一句点醒我的话反过来想后来我请教了身边一个刷题量很大的朋友他一句话点醒我“你别每个1都去找0你把所有0先放到队列里让它们一起往外面扩散。”这句话当场让我愣了半秒。是啊如果让所有 0 同时作为起点一起向外一层一层扩散每个格子第一次被扩散到的时候那个层数就是它到最近 0 的距离。这个操作本质上就是多源 BFS把所有 0 看成一个整体源点一次性往外推。这比每个 1 单独 BFS 快太多了一遍扫描就能把所有答案填完。也是从这道题开始我遇到“矩阵 最短距离 只有0/1”这类组合第一反应不再是“对每个目标点单独搜”而是“能不能把多个起点合并成一个多源起点”。这个思维转变比背十道模板题都管用。2. 多源 BFS 的原理拆解为什么它能一波推平2.1 把矩阵看作一张网格图理解多源 BFS得先把矩阵转化为图。每个格子是图里的一个节点上下左右相邻的格子之间有一条边边的权重都是 1。所谓“离最近的0的距离”其实就是这个格点到某个值为0的格点的最短路径长度。BFS 之所以适合这张图是因为所有边的权重一样。BFS 从起点出发按层扩展第一次到达某个节点时走的步数一定是从起点到该节点的最短路径。这个性质是 BFS 在无权图中天然成立的不需要证明直觉上就是一层一层扩散谁先碰到谁就是最近的。2.2 多源起点的正确性虚拟源点如果只有一个 0那问题很直接从这个 0 做单源 BFS 就行。但矩阵里可能有几十个 0怎么做最优雅的理解方式是你可以在所有 0 节点的外面再想象一个虚拟的超级源点它到每个 0 节点都有一条权重为 0 的边。从这个超级源点出发做 BFS第一波先同时走到所有 0 节点之后的过程就和普通 BFS 一模一样。因为超级源点到每个 0 的权都是 0所以所有 0 节点在 BFS 的第一层就被同时访问到接下来所有格子第一次被访问时的层数就等于它到最近 0 的距离。这就是多源 BFS 的理论基础。实现的时候你不用真的建虚拟源点直接把所有值为 0 的格子塞进队列再把它们标记为“已访问”效果完全等价。2.3 为什么“先入队”和“先访问”很重要多源 BFS 里有一个我一开始忽略的细节必须把起点在入队时就标记为已访问而不是出队时再标记。如果出队才标记同一个节点可能被多个源点重复加入队列不仅多干活还可能把距离值覆盖错。这道题数据小的时候看不出问题矩阵一大队列里全是重复节点内存和耗时一起崩。这个细节本质上就是 BFS 的“状态去重”。所有节点只有第一次被访问时才需要处理后面再碰到直接跳过。先入队再标记正好能保证每个节点最多进队一次。这也直接决定了多源 BFS 的总复杂度是 O(m×n)每个格子进队一次、出队一次。3. 解法一多源 BFS 的完整实现与细节3.1 算法步骤逐条拆解写代码之前先把过程梳理成可执行的步骤创建一个队列遍历整个矩阵把所有等于 0 的格子坐标一次性入队同时用一个额外的二维数组记录“已经访问过”或者直接在原矩阵上标记。对每个入队的 0 格子它的距离初始化为 0如果使用独立的结果数组那这些位置直接填 0。开始 BFS 循环从队列中取出一个格子检查它上、下、左、右四个邻居。如果邻居在矩阵范围内并且还没有被访问过就把它加入队列并将其距离设置为当前格子距离 1。重复直到队列为空。此时所有 1 格子的距离都已经被填好。有两点需要特别说明。第一为什么要让所有 0 先入队因为只有让它们同时开始扩散才能保证“谁先到谁最近”。第二为什么距离是“当前格子距离 1”因为从当前格子走到邻居正好多了一步而且这是该邻居第一次被访问所以这个距离一定是最短距离。3.2 逐步推演拿一个具体矩阵走一遍用刚才那个矩阵来模拟初始: [[0, 0, 0], [0, 1, 1], [1, 1, 1]]队列初始化后里面是四个 0 坐标。第一轮出队的是 (0,0)四个邻居里 (0,1) 是 0 已经访问过(1,0) 也是 0(0,0) 邻居里没有未访问的 1继续下一个。四个 0 依次出队后轮到这些 0 的邻居。以 (1,1) 为例它第一次被访问时是从 (1,0) 或者 (0,1) 过去的距离是 1所以结果矩阵第 1 行第 1 列填 1。接着 (1,1) 会入队它的邻居 (2,1) 会被访问距离是 2。类似地(1,2) 被访问时距离为 1然后 (2,2) 通过 (1,2) 被访问到距离为 2。最终结果[[0, 0, 0], [0, 1, 1], [1, 2, 2]]是不是和输出一模一样核心过程就是把所有 0 先铺成一圈“防护带”每个非 0 格子都在被某个 0 扩散到的那一刻拿到正确答案。3.3 Python 实现可直接复制的版本from collections import deque from typing import List class Solution: def updateMatrix(self, mat: List[List[int]]) - List[List[int]]: m, n len(mat), len(mat[0]) dist [[0] * n for _ in range(m)] visited [[False] * n for _ in range(m)] q deque() # 所有 0 先入队作为多源起点 for i in range(m): for j in range(n): if mat[i][j] 0: q.append((i, j)) visited[i][j] True directions [(1, 0), (-1, 0), (0, 1), (0, -1)] while q: x, y q.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx m and 0 ny n and not visited[nx][ny]: visited[nx][ny] True dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) return dist这段代码的时间复杂度是 O(m×n)因为每个格子最多入队一次、出队一次。空间复杂度同样是 O(m×n)由 visited 数组、dist 数组和队列共同构成。3.4 一个可以继续优化的点原地修改省空间如果你不想额外开 visited 数组和 dist 数组可以直接在原始矩阵上修改。做法是先遍历一次矩阵把所有 1 改成一个大数比如 -1表示“未访问”。0 保持不变入队。然后在 BFS 过程中遇到值为 -1 的邻居就直接把它更新成当前格子值 1再入队。from collections import deque from typing import List class Solution: def updateMatrix(self, mat: List[List[int]]) - List[List[int]]: m, n len(mat), len(mat[0]) q deque() for i in range(m): for j in range(n): if mat[i][j] 1: mat[i][j] -1 # 用 -1 标记未访问的 1 else: q.append((i, j)) # 0 入队 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] while q: x, y q.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx m and 0 ny n and mat[nx][ny] -1: mat[nx][ny] mat[x][y] 1 q.append((nx, ny)) return mat这里有个经验之谈原地修改虽然省空间但会破坏原始数据。如果面试官没明确说可以改输入最好先问一句。实际工程里输入数组往往要复用改坏了不太好交代。刷题场景为了省事可以原地改但心里要清楚这个 trade-off。4. 解法二两趟遍历的动态规划4.1 DP 状态定义与递推思路除了 BFS0-1 矩阵还有另一种非常经典的解法就是动态规划。思路也很直接一个格子 (i, j) 到最近 0 的距离要么来自上方 ((i-1, j))要么来自下方 ((i1, j))要么来自左方 ((i, j-1))要么来自右方 ((i, j1))取这四个方向的最小值再加 1。但问题在于这四个方向的信息没法一次性全部获得。一次遍历只能从已知区域向外推导比如从左上角往右下遍历时当前位置只能参考上方和左方的格子因为下方和右方还没算出来。所以需要用两次遍历第一趟从左上角到右下角处理“来自上方或左方”的路径。第二趟从右下角到左上角处理“来自下方或右方”的路径。两趟都做完每个格子考虑到了四个方向答案就完整了。4.2 递推公式与初始化初始化时矩阵里原本为 0 的格子距离为 0原本为 1 的格子先设置成一个非常大的数比如 1000000方便后续取 min。第一趟遍历对每个格子 (i, j)如果它是 0跳过。如果它不是 0看它的上方邻居 (i-1, j) 和左方邻居 (i, j-1)如果存在就尝试dp[i][j] min(dp[i][j], dp[i-1][j] 1, dp[i][j-1] 1)。第二趟遍历方向反过来从右下角开始。对每个格子看它的下方邻居 (i1, j) 和右方邻居 (i, j1)如果存在就尝试dp[i][j] min(dp[i][j], dp[i1][j] 1, dp[i][j1] 1)。为什么两次遍历就能覆盖所有情况因为一个格子到最近 0 的最短路径无论怎么走它到达当前格子的最后一步一定是来自四个方向之一。第一趟把“从上往下、从左往右”方向走到的路径考虑完第二趟把“从下往上、从右往左”方向走到的路径补齐。两边一合并所有可能的最短路径都被覆盖到了。4.3 以具体矩阵推演 DP 两趟过程还是用同一个例子初始: [[0, 0, 0], [0, 1, 1], [1, 1, 1]]先初始化0 保持不变1 变成大数[[0, 0, 0], [0, inf, inf], [inf, inf, inf]]第一趟从左上往右下(0,0)(0,1)(0,2) 都是 0不动。(1,0) 是 0不动。(1,1)上方 (0,1) 是 0左方 (1,0) 是 0所以更新成 min(inf, 01, 01) 1。(1,2)上方 (0,2) 是 0左方 (1,1) 现在是 1所以更新成 min(inf, 01, 11) 1。(2,0)上方 (1,0) 是 0没有左方所以是 1。(2,1)上方 (1,1) 现在是 1左方 (2,0) 是 1所以更新成 min(inf, 11, 11) 2。(2,2)上方 (1,2) 现在是 1左方 (2,1) 是 2所以更新成 min(inf, 11, 21) 2。第一趟结束[[0, 0, 0], [0, 1, 1], [1, 2, 2]]咦这个例子一遍就出答案了。但这不是普遍情况。如果矩阵的 0 全在右下角第一趟推出来的距离就会偏大第二趟才会把它修正。比如[[1, 1, 1], [1, 1, 0]]第一趟从左上往右下(0,0)没有上方和左方保持 inf。(0,1)左方 inf保持 inf。(0,2)左方 inf保持 inf。(1,0)上方 inf保持 inf。(1,1)上方 inf、左方 inf保持 inf。(1,2)是 0不动。第一趟之后(1,1) 还是 inf这显然不对它离最近的 0 只有 1 步。第二趟从右下往左上(1,2) 是 0不动。(1,1)右方 (1,2)0下方没有更新成 1。(1,0)右方 (1,1)1更新成 2。(0,2)下方 (1,2)0更新成 1。(0,1)右方 (0,2)1下方 (1,1)1更新成 2。(0,0)右方 (0,1)2下方 (1,0)2更新成 3。最终[[3, 2, 1], [2, 1, 0]]完全正确。所以两趟遍历缺一不可。这也是 DP 解法最容易被忽略的点——单趟遍历只能利用局部方向的信息想覆盖全局必须正反各来一次。4.4 Python 实现与两种解法对比from typing import List class Solution: def updateMatrix(self, mat: List[List[int]]) - List[List[int]]: m, n len(mat), len(mat[0]) INF 10**9 dp [[INF] * n for _ in range(m)] # 初始化0 的位置是 01 的位置保持 INF for i in range(m): for j in range(n): if mat[i][j] 0: dp[i][j] 0 # 第一趟左上 - 右下 for i in range(m): for j in range(n): if dp[i][j] 0: continue if i 0: dp[i][j] min(dp[i][j], dp[i - 1][j] 1) if j 0: dp[i][j] min(dp[i][j], dp[i][j - 1] 1) # 第二趟右下 - 左上 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): if dp[i][j] 0: continue if i m - 1: dp[i][j] min(dp[i][j], dp[i 1][j] 1) if j n - 1: dp[i][j] min(dp[i][j], dp[i][j 1] 1) return dp把两种方法放在一起比较可以这样看维度多源 BFS两趟 DP时间复杂度O(m×n)O(m×n)空间复杂度队列 额外数组最坏 O(m×n)只需要 DP 数组O(m×n)代码直观度更符合“扩散”直觉需要理解两次递推的组合逻辑边界情况更容易被边界条件坑到思路清晰后不容易漏面试沟通容易讲解配合图示效果好简洁但是需要递推推导从我个人的刷题经验看如果面试时间充裕先讲 BFS 再讲 DP 是最稳妥的答题路径。BFS 负责“让面试官快速理解你在做什么”DP 负责“展示你有优化意识”。两个解法都写出来比只用一种解法更能体现题感。5. 易错点、边界情况与面试实战经验5.1 我踩过的三个典型坑第一个坑就是最开始的“每个1单独BFS”复杂度爆炸前文已经讲过。这里想说的是怎么提前识别这种“单个搜索不可行”的模型。核心规律是当目标点数量巨大、且每个目标点都需要同类型的搜索时马上思考多源合并。不仅仅是 0-1 矩阵很多图论题都有类似的套路。第二个坑是“已访问”标记的位置。我写 BFS 的时候很容易在出队时才标记 visited。遇到有环的图这会导致同一个节点被入队多次。0-1 矩阵里虽然没有环但多个 0 源点同时扩张时同一个 1 可能被多个邻居重复发现。出队标记会让这个 1 被重复处理好几轮。正确做法是入队的同时立刻标记。第三个坑是 DP 解法只做单向遍历。只从左上往右下跑一遍遇到 0 全部集中在右下角的用例答案就会全错。这个问题在 LeetCode 的测试用例里几乎是必现的只要矩阵稍微大一点、0 分布不均单向 DP 就现原形。所以写 DP 两趟法时建议直接固定住“第一趟左上到右下、第二趟右下到左上”的记忆点别临时想。5.2 边界情况写代码前先列出来刷题这么多年我养成了一个习惯拿到题目先不写代码把边界情况写在草稿纸上。0-1 矩阵的边界情况主要有这么几类矩阵只有一行比如[[1, 0, 1]]。此时上下方向不存在DP 的i 0判断会挡住越界BFS 的方向数组也能正常处理。矩阵只有一列比如[[1], [0], [1]]。同理左右方向不存在。矩阵里没有 0全是 1。题目如果保证至少有一个 0那就没事如果不保证输出矩阵会全部保持 INF 或初始值。我一般会在开头问面试官“是否保证输入中至少存在一个 0”。矩阵里全是 0。这种情况结果全是 0BFS 和 DP 都能直接跑出来但代码里如果依赖“遇到 1 才处理”要注意别把 0 的距离误改。边界情况单独用一组小样例测一下比什么都管用。我在本地写题时习惯直接构造一个[[1]]的单元素矩阵一个[[1, 0], [0, 1]]的对称矩阵再加一个 0 全部在角落的大矩阵三个测完基本能覆盖九成的问题。5.3 面试官问变体我怎么应对这道题最常见的变体是把方向改成“可以斜着走”那距离定义就不再是曼哈顿距离而是切比雪夫距离。这种变体下多源 BFS 的方向数组要从 4 个方向扩到 8 个方向DP 的两趟遍历就不够用了因为斜向信息无法靠四个方向的递推覆盖全。如果面试官这么问优先回到 BFS。另一种变体是“矩阵里不是 0/1而是 0/1/2要求每个格子到最近的非 0 值比如只认 2的距离”。处理方式完全一样把 2 作为多源起点即可。所以 0-1 矩阵这道题的本质其实是“怎么从多个指定起点同时做无权图的最短路径搜索”抓住这个本质变体再多也能举一反三。还有一类变体是“要求你在原矩阵上原地修改并且不能额外开 visited 数组”。那就用我前面写的“-1 表示未访问”技巧。这里有一个细节用 -1 标记未访问前提是矩阵原本只有 0 和 1没有 -1否则会冲突。实际面试中如果不确定可以先用一个很大的正数表示“未计算”比如 INF只要不影响到最终结果就行。5.4 复盘经验错题本上应该记什么这道题最终写在错题本上的不是“标准答案代码”而是三个教训第一思维定式要不得。看到“最近”“距离”就条件反射地对每个目标点单独搜索是应试套路的后遗症。真正有价值的思考是反问一句能不能把所有源点合并让搜索只做一遍第二正确空间复杂度的来源是“每个节点只处理一次”。不管是 BFS 的 visited 数组还是 DP 的两次遍历本质上都在保证状态计算不重复。第三边界情况必须主动列出来不要等测试用例来打脸。我把这三个教训连同题目编号“69”一起记下来每次复习旧的错题时都会扫到。说实话这道题本身不算难但给我留下的印象很深因为它逼着我跳出“点到点”的旧框架学会“多点汇流”的思考方式。之后再遇到岛屿类问题、腐烂的橘子问题、墙与门问题我都能第一时间想到多源 BFS都是拜这次翻车所赐。最后再分享一个实际做题时的小技巧在编辑器里先写一版“能跑通但可能超时”的暴力 BFS然后用它生成小矩阵的正确答案再去验证多源 BFS 和 DP 写出来的结果是否一致。这个方法能帮你快速定位到底是思路错了还是代码细节错了我后来做这一类矩阵题都用这个方式自测省了不少调试时间。如果你也正在为这类“看起来不难但总是差一点”的题烦恼别急着刷题量先把这一题吃透。从错误中抽出来的底层思维往往比一百道“直接过”的题更有价值。