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