企业官网建设流程全解析

前段时间有朋友在准备算法面试，把一些高频题重新拉出来过了一遍。有一道题让我印象特别深——题目叫“矩阵距离”，解法核心是多源 BFS。这题出现在某家自动驾驶公司的面试题库里，题面本身非常朴素：给一个 01 矩阵，算出每个格子到最近的 1 的距离。第一次见的人可能会觉得，这不就是个 BFS 吗？但真把思路讲清楚、代码写利索、再把面试官可能的追问一一接住，其实非常考验基本功。这篇文章我打算从题目拆解、多源 BFS 的思维模型、代码实现、复杂度分析、变体题和工程落地几个角度，把这道题完整讲透。适合正在准备面试的开发者，也适合想真正搞懂 BFS 本质的初学者。

1. 先把题目读透：输入输出与背后意图

1.1 题面长什么样

题目的标准描述是这样的：给定一个 N 行 M 列的 01 矩阵 matrix，矩阵元素只有 0 和 1。要求输出一个同样大小的矩阵 dist，其中 dist[i][j] 表示从格子 (i, j) 出发，只允许向上下左右四个方向移动，到达任意一个值为 1 的格子所需的最短步数。如果当前格子本身就是 1，距离记 0。

举个具体的例子。

输入矩阵： 0 0 1 0 0 0 0 1 0

对应的输出应该是：

2 1 0 2 1 1 1 0 1

我手动验证一下：左上角的 (0,0)，最近的 1 在 (0,2)，走过去要两步，所以是 2。中间的 (1,1)，最近的 1 就在正下方 (2,1)，一步到位，所以是 1。右下角的 (2,2)，最近的 1 是左边的 (2,1)，距离也是 1。这里说的距离，是曼哈顿距离，也就是 |x1 - x2| + |y1 - y2|，因为每一步只允许上下左右移动，不能斜着走。

有一点值得先说清楚：这种题有两种常见问法，一种是“每个 0 找最近的 1”，另一种是“每个 1 找最近的 0”。有些在线评测平台上的 01 矩阵题，就是反过来求的。很多人把这两个版本记成两套解法，其实大可不必——算法骨架完全一样，唯一需要改的，就是一开始把哪些格子当作源点放进队列。后面我会反复强调这一点，它是理解多源 BFS 的关键。

1.2 为什么自动驾驶公司会把这道题放进题库

我第一次看到这道题出现在自动驾驶公司的面试题里时，第一反应是：这也能当面试题？后来想明白了，它背后是有真实业务影子的。

自动驾驶里，环境经常被表示成栅格地图：把车辆周围的空间切成一个个小格子，每个格子要么是空闲的（0），要么是被障碍物占据的（1）。规划模块在决定走哪条路之前，通常要算每个空闲格子到最近障碍物的距离。有了这张“障碍物距离图”，才能做障碍物膨胀、安全边距判定、碰撞风险梯度计算。这不就是矩阵距离问题吗？栅格地图足够大的时候，连续做几万次暴力搜索根本不现实，必须用一次多源 BFS 在 O(N*M) 内把整张距离图算出来。

所以面试官问这道题，表面上是考 BFS，实际上是看你能不能把一个基础的图遍历算法，跟工程场景里的“距离变换”对上号。它不考察你背了多少模板，而是考察你能不能把一个朴素问题在资源约束下做到最优复杂度，并且把边界条件处理干净。这也是我建议所有准备算法面试的人，不要只背代码，一定要理解题目为什么这么问的原因。

2. 多源 BFS 的思路是怎么一步步长出来的

2.1 先看暴力解法为什么顶不住

拿到这道题，最直觉的做法是“对每个 1 跑一遍 BFS”：先找到一个 1，把它当作起点向外扩散，碰到 0 就更新距离；然后再找下一个 1，继续更新。这个方案复杂度是多少？

假设矩阵有 N 行 M 列，总共有 k 个 1。每跑一次 BFS 是 O(NM)，跑 k 次就是 O(kNM)。在全是 1 和 0 交错分布的矩阵里，k 可以接近 NM 的一半。算一下：1000×1000 的矩阵，总共 10^6 个格子，k 大约是 5×10^5，总操作量是 5×10^11 这个量级，任何在线评测系统都会直接超时，更不用说自动驾驶里动辄几万乘几万的栅格地图了。

还有个更笨的办法是枚举所有 0 和所有 1 的组合，两两算曼哈顿距离，那就是 O((N*M)^2)，更没戏。所以我们必须找到一种只遍历一遍就能得出所有答案的办法，多源 BFS 就是干这个的。

2.2 一个生活化类比：多支队伍同时出发扩散

为什么叫“多源 BFS”？因为传统的 BFS 只有一个起点，从起点向外一层一层扩展。多源 BFS 则允许把多个起点同时放进队列，让信息像水波一样从所有起点同时向外扩散。

打个比方。假设矩阵里每个 1 都是一个营地，每个营地都派出一支小队，所有小队在同一时刻出发，每走一格花一分钟，并且步调完全一致。任何格子，哪支小队先到，就归谁记录距离。因为所有小队速度相同，先到的那个，必然是离它最近的营地派出来的。这个“同时出发、同时扩散、先到先得”的过程，就是多源 BFS 的完整意象。

这和“逐个营地把所有小队派出去各跑一遍”有本质区别。逐个派的话，后出发的小队会重复走先出发的队伍已经走过的路，白白浪费时间。而同时出发时，每个格子只被最早到达的队伍“认领”一次，整张图只用遍历一遍。这就是复杂度从 O(kNM) 降到 O(N*M) 的根本原因。

2.3 为什么 BFS 天然保证第一次到达就是最短距离

BFS 有一个非常重要的性质：它是严格按层扩展的。起点在第 0 层，起点能一步到达的格子在算第 1 层，能两步到达的在第 2 层，依此类推。队列里的元素顺序，永远保证先弹出的是距离更小的格子。

在多源 BFS 里，所有源点在初始化时都是第 0 层，统一入队。接下来弹出的所有邻居都是第 1 层，然后第 2 层，逐层推进。某一个格子被第一次访问到时，它正处于从小到大的某一层上，也就是说我们是在所有可能路径里，第一个碰到它的那条路径上把它拿下的。如果存在一条更短的路径，那个更短的路径会先到达这个格子，这跟“第一次访问”矛盾。所以第一次访问的层号，必然等于最短距离。

用图论的视角看，这就是边权全为 1 的图上跑迪杰斯特拉（Dijkstra）的简化版。因为所有边权相等，优先级队列退化成普通队列，先入先出就是按距离排序。很多教材把 BFS 当作独立算法讲，其实它就是 Dijkstra 在无权图上的特例，理解了这一层，面试里被问到“BFS 和 Dijkstra 的关系”也能从容接住。

3. 手把手实现：代码、细节与现场手写要点

3.1 Python 实现与逐行解读

我平时写这类题，习惯用 Python 练思路，因为它表达起来最直接。下面这个版本，就是我在面试模拟里最常写的。

from collections import deque def matrix_distance(grid): if not grid or not grid[0]: return [] m, n = len(grid), len(grid[0]) dist = [[-1] * n for _ in range(m)] q = deque() # 第一步：把所有源点（值为 1 的格子）入队，距离记为 0 for i in range(m): for j in range(n): if grid[i][j] == 1: dist[i][j] = 0 q.append((i, j)) # 四个方向的增量：上、下、左、右 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 dist[nx][ny] == -1: dist[nx][ny] = dist[x][y] + 1 q.append((nx, ny)) return dist

这里有几个关键设计。第一，dist 数组初始化为 -1，而不是很大的数。-1 同时承担了两个职责：表示“还没被访问过”，以及哨兵值。因为距离永远是非负数，所以 -1 不可能跟合法距离冲突，省掉了一个单独的 visited 数组。第二，入队前统一判断边界，防止数组越界。第三，所有源点先全部入队，再进入 while 循环，顺序不能反，否则就退化成了多个独立的单源 BFS。

3.2 C++ 面试手写版本

如果面试现场要求手写，我一般写 C++，因为自动驾驶公司的高频语言就是 C++。核心逻辑完全一致。

#include <vector> #include <queue> using namespace std; vector<vector<int>> updateDistance(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dist(m, vector<int>(n, -1)); queue<pair<int, int>> q; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { dist[i][j] = 0; q.push({i, j}); } } } int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int k = 0; k < 4; ++k) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } } return dist; }

这版代码里用了 C++17 的结构化绑定auto [x, y]，写起来很顺手。如果面试官的环境比较老，不支持 C++17，就换成int x = q.front().first; int y = q.front().second;，一样能过。

3.3 方向数组、哨兵值与边界检查的那些坑

这段是很多人真正上手时会踩坑的地方，我列几个最常见的：

方向数组最容易写错。4 向移动是上下左右，对应dx = {-1,1,0,0},dy = {0,0,-1,1}。如果题面改成可以斜着走，就要扩展成 8 个方向，这时距离的含义变成切比雪夫距离，BFS 依然成立，因为 BFS 只要求“一步”的定义一致，不管一步是在哪个方向。

边界检查必须放在数组访问之前。nx >= 0 && nx < m && ny >= 0 && ny < n这个顺序不能乱写，更不能不写。很多初学者图省事，先访问再判断，结果直接越界崩溃。

哨兵值的选择会影响代码简洁度。用 -1 的话，判断条件一行搞定；用一个大数 INF 的话，通常要写成dist[nx][ny] > dist[x][y] + 1，也能工作，但每次都要比较大小，代码略啰嗦。我更推荐 -1。

还有个隐藏问题：如果你决定原地修改输入矩阵，把距离直接写回 grid，那么源点的 1 会被改成 0。在 BFS 过程中，如果你再用grid[nx][ny] == 1来判断是不是源点，就会出现逻辑错误，因为已经被改写成距离数值了。原地写法不是不行，但必须把所有源点先入队，并且后续用 dist 数组或单独的 visited 标记来做判断，别指望原始矩阵里的 1 还能一直保留。为了省一点空间把逻辑搞复杂，面试时不太划算，我通常直接开一个新的 dist 数组。

4. 复杂度账本与多种解法的对比

4.1 时间与空间复杂度的严谨推导

多源 BFS 的时间复杂度为什么是 O(NM)？关键在“每个格子最多入队一次”。源点在第一阶段全部入队，之后每访问一个格子，就把四个邻居检查一遍，遇到没访问过的才入队。因此每个格子只会被当作邻居检查 4 次，总操作量是 4NM，常数可以忽略，最终就是 O(NM)。

空间复杂度拆成两部分。dist 数组本身要存 NM 个整数，是 O(NM)。队列在最坏情况下能装多少元素？理论上不会超过图上所有点，所以是 O(NM) 的上界；实际跑起来，队列里同时存的是某一层和下一层的边界点，通常是 O(N+M) 的数量级，因为一层波的轮廓线就横跨那么长。所以总空间复杂度写 O(NM) 是严格安全的。

这个“每个格子只处理一次”的性质，也解释了前面暴力法为什么慢：单个 BFS 本来也只用 O(N*M)，但外面套了 k 次循环，把同样的区域反复走了 k 遍。多源 BFS 把“反复走”变成“一次走完”，本质上是把多个 BFS 的重复子问题合并了。

4.2 两遍动态规划：另一种 O(N*M) 的解法

除了多源 BFS，这道题还有一个经典的 O(N*M) 解法：两遍动态规划。思路是，最近的那个 1，相对于当前格子 (i, j) 来说，一定在四个象限的某一个方向。第一遍从左上往右下扫，只考虑“从上方或左方走过来”的路径；第二遍从右下往左上扫，只考虑“从下方或右方走过来”的路径。两遍合在一起，就覆盖了所有可能的最短路径方向。

我把这个解法也写出来，方便对比。

def matrix_distance_dp(grid): m, n = len(grid), len(grid[0]) INF = 10 ** 9 dist = [[INF] * n for _ in range(m)] for i in range(m): for j in range(n): if grid[i][j] == 1: dist[i][j] = 0 else: if i > 0: dist[i][j] = min(dist[i][j], dist[i-1][j] + 1) if j > 0: dist[i][j] = min(dist[i][j], dist[i][j-1] + 1) for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): if grid[i][j] != 1: if i < m - 1: dist[i][j] = min(dist[i][j], dist[i+1][j] + 1) if j < n - 1: dist[i][j] = min(dist[i][j], dist[i][j+1] + 1) return dist

这个解法在无障碍的普通网格上是正确的，但有两个问题。第一，它依赖“最短路径可以分解成只含两个方向的一段单调路径”这个前提，需要额外论证，面试现场容易讲不清楚。第二，一旦网格里出现障碍物，最短路径可能需要绕路，路径方向不再是单调的，两遍 DP 就不再成立了，而多源 BFS 只需要在判断邻居时把障碍物格子跳过就行。所以除非面试官明确让你尝试 DP，否则多源 BFS 是更稳、更通用的答案。

4.3 不同方案怎么选：一张表说清楚

面试场景里，我首选多源 BFS，其次才是两遍 DP。多源 BFS 的每一步都可以用“水波扩散”来解释，面试官也容易跟上，正确性论证一句话就能说清：先到先得，第一次访问就是最短距离。

5. 面试追问、变体题与工程落地

5.1 面试官常用的六个追问

这道题最精彩的部分不在题面，而在追问。我整理了几个我在模拟面试和真实面经里见到的高频追问，每个都值得提前准备。

如果网格里有障碍物，比如 -1 表示不可通行，怎么改？多源 BFS 几乎不用改，检查邻居时跳过障碍物格子即可。但两遍 DP 会失效，因为绕路后路径不再单调。

如果是 8 方向移动，距离定义变成切比雪夫距离，怎么办？把方向数组扩成 8 个，BFS 依然正确，因为 BFS 只关心“一步能到哪”，不关心一步的几何含义。

如果不仅要每个格子的最近距离，还要找“离所有 1 最远的 0”，怎么做？多源 BFS 全部算完后，扫一遍 dist 数组，找出值为 0 的格子里的最大距离。这是同一个模板的常见变体。

如果距离改成欧氏距离呢？BFS 就不好使了，因为欧氏距离不满足“沿四方向步数累积”的性质。这时要上距离变换算法，或者用 KD 树做最近邻查询，属于另一个话题。

如果矩阵特别大，比如 20000×20000，内存怎么办？距离值可以用短整型甚至字节型存储，上限封顶；还可以分块并行，每个线程算一块，再在边界处做一次合并。初版实现直接全量算 O(N*M) 也能扛，但工程上总有优化空间。

如果障碍物在车辆行驶中不断变化，距离图需要实时更新怎么办？每次都全量重算很浪费，可以考虑增量式距离变换，只重算受影响区域。这个追问基本就进入自动驾驶工程面了。

5.2 一道高价值变体：最远海洋点问题

我在多个面试题库里见过这道题的变体：“给定一个栅格，1 表示陆地，0 表示海洋，找到距离陆地最远的海洋格子，并返回这个最大距离。”

它的解法就是多源 BFS，唯一的变化是 BFS 过程中维护一个最大值。所有陆地格子先入队，距离记 0；海洋格子逐层被访问，距离不断增加；BFS 结束后，扫一遍所有海洋格子的距离取最大值即可。如果整张图没有陆地，或者没有海洋，直接返回 -1，这是题目要求的边界情况。

这个变体跟原题共享 95% 的代码，但考察点多了一层：你能不能把“求最近距离”的任务，改造成“求最近距离中的最大值”。面试时遇到变体题，先冷静下来，想清楚题目是不是在同一个模板上加了一个统计步骤，往往就能快速下手。

5.3 从题目到自动驾驶栅格地图的桥

说回开头提到的工程场景。自动驾驶里，障碍物距离图有很多用途。最典型的是“障碍物膨胀”：把障碍物周围的格子按照安全距离阈值标记为不可通行或高风险区域，这个阈值判定就来源于距离图。有了逐格距离，还可以构造代价地图，让路径规划器在离障碍物越近的地方代价越高，从而引导车辆走“居中”的安全路线。

再往深一点，距离图的梯度信息还能用来判断车辆的哪个方向更安全：如果车辆当前位置到最近障碍物的距离小于车身宽度的一半，就可以认为有碰撞风险。这些计算每天在一个实时系统里高频执行，算法选错的代价不只是超时，而是整个规划栈的性能瓶颈。一个能把矩阵距离用多源 BFS 写清楚的候选人，至少说明他有能力把这种基础模块做扎实。这也是为什么这类看起来简单的题，会出现在自动驾驶研发岗的面试里。

6. 实际跑题时的高频问题与排查实录

6.1 高频报错与原因速查

6.2 一次现场手写踩坑记录

我自己就栽过一次：那次是在白板上写原地修改版本，思路是直接把距离写回 grid。初始化阶段没问题，把所有 1 改成 0 并入队。问题出在 BFS 里，我没用额外的 visited 标记，而是靠检查grid[nx][ny] == 0来判断“这个格子是不是还没被访问过”。结果扩散了几层之后，越来越多的格子被写成了距离数字，条件判断开始乱七八糟，有的格子被重复入队，有的格子该更新却没更新。最后在面试官提醒下换成了独立 dist 数组，代码立刻干净了。

那次之后我总结了一个原则：面试手写题，除非有明确的内存压力提示，否则优先选择逻辑更清晰的方案。一个独立 dist 数组多花 O(N*M) 的空间，换来的是判断条件简单、不容易出错。节省空间的“聪明”写法，留到实际需要时再用。

6.3 面试手写代码的三个小建议

写之前先澄清关键语义。问清楚是 0 找最近的 1，还是 1 找最近的 0；是 4 方向还是 8 方向；能不能原地修改。这几个问题一抛出来，面试官就知道你有工程沟通意识。

写的时候把“源点入队”和“逐层扩散”两步分开讲。我的习惯是先说出思路：“先把所有 1 放入队列，然后 BFS 逐层扩展”，再动手写代码。边说边写，能让面试官始终跟上你的节奏。

写完之后主动报复杂度。很多人写完就不说话了，其实这时候只要补一句“每个格子最多入队一次，所以时间 O(NM)，空间 O(NM)”，整个答案的完整性立刻提升一个档次。还可以顺带补一句：如果需要处理障碍物，在这里加一个跳过条件就行。

我个人在实际带新人做题时最大的体会是，多源 BFS 的核心不是什么炫技算法，而是一个思维模型：当你需要求“每个点到最近一类点”的距离时，把源点整体入队，让信息像水波一样同时向外扩散。这个模型想通了，矩阵距离、最远海洋点、障碍物膨胀距离图，全都是一套代码的变体。面试里能把“为什么同时扩散是最优的”这句话讲清楚，通常比默默写完代码更有加分作用。最后再分享一个小技巧：写完代码不要急着交，拿我刚才那个 3×3 的小矩阵在脑子里手动跑一遍，检查输出对不对。这一步花不了十秒钟，但能拦住九成以上的低级错误。