1. 从一道题看透网格BFS地图分析到底在考什么LeetCode上标签为“中等”的题目里有一类题特别有意思——它表面上是地图、海洋、陆地的故事骨子里考的却是多源广度优先搜索。地图分析就是这类题的典型代表。题目描述很直白给你一个N×N的网格每个格子要么是陆地1要么是海洋0要求你找到一个海洋格子使得它到最近陆地的曼哈顿距离最大返回这个最大距离如果全是陆地或者全是海洋返回-1。我第一次看到这道题的时候脑子里第一反应是暴力——对每个海洋格子做一次BFS找最近的陆地然后取最大值。这个思路没错但复杂度直接飙到O(N^4)N稍微大一点就超时。后来才反应过来这题的正确打开方式是把所有陆地当作起点同时向外扩散一层一层地“淹没”海洋最后被淹没的那层海洋就是离陆地最远的。这就是多源BFS的核心思想。这篇文章我会从题目分析、思路演进、代码实现、复杂度优化、常见坑点几个维度把地图分析这道题彻底讲透。不管你是刚接触BFS的新手还是想复习图论算法的老手都能从中拿到可以直接复用的东西。尤其是多源BFS这个技巧在岛屿问题、腐烂橘子、01矩阵等一大票题目里都能直接套用学会一道题等于学会一类题。2. 题目拆解与核心需求分析2.1 题目到底在问什么先把题目翻译成人话。你有一个正方形的网格地图1代表陆地0代表海洋。对于每一个海洋格子你计算它到所有陆地格子中距离最近的那个距离值。然后在这些“最近距离”里找出一个最大值返回它。如果地图上没有海洋或者没有陆地返回-1。这里的关键点有三个第一距离的定义是曼哈顿距离也就是横坐标差的绝对值加上纵坐标差的绝对值不是欧几里得距离第二是“最近的陆地”不是“所有陆地的平均”或者“最远的陆地”第三要求的是所有海洋格子中“最近陆地距离”的最大值不是某个特定海洋格子的值。举个例子假设网格是[[1,0,1],[0,0,0],[1,0,1]]四个角是陆地中间和四条边的中点是海洋。对于正中间的海洋格子(1,1)它到四个陆地的距离都是2所以最近距离是2。对于边中点的海洋格子比如(0,1)它到(0,0)和(0,2)的距离都是1最近距离是1。所以最终答案是2。2.2 为什么暴力法不可取最直观的做法是两层循环遍历每个海洋格子对每个海洋格子再做一次BFS找最近的陆地。假设网格是N×N外层遍历是O(N^2)每个海洋格子BFS最坏情况要遍历整个网格又是O(N^2)总复杂度O(N^4)。N100的时候就是10^8级别N200直接爆炸。有人可能会想那我能不能用动态规划从四个方向分别扫描这个思路其实是可行的后面我会详细讲。但最优雅、最容易理解、也最容易扩展到其他题目的方法还是多源BFS。它的复杂度是O(N^2)每个格子只被访问一次干净利落。2.3 多源BFS的核心洞察多源BFS的精髓在于一个思维转换与其从每个海洋出发找陆地不如从所有陆地同时出发找海洋。你可以想象所有陆地格子在第一时刻同时向四周扩散第一层扩散到的海洋格子距离为1第二层扩散到的距离为2以此类推。最后被扩散到的那个海洋格子它的距离就是最大值。这个转换为什么成立因为BFS本身就是按距离层序遍历的。单源BFS从起点出发第k层就是距离起点为k的所有节点。多源BFS只是把多个起点同时放进队列第k层就是距离最近起点为k的所有节点。对于每个海洋格子它第一次被访问到的层数就是它到最近陆地的距离。而最后被访问到的那个格子自然就是距离最大的。注意多源BFS要求所有源点同时入队并且初始距离都设为0。不能一个一个源点分别做BFS再取最小值那样复杂度会退化。3. 多源BFS的实现细节与代码拆解3.1 算法流程一步步拆解整个算法的流程可以拆成五步遍历整个网格把所有陆地格子值为1的坐标加入队列同时记录陆地数量。如果陆地数量为0或者等于N×N直接返回-1。初始化距离变量distance为-1用于记录最后扩散到的层数。开始BFS循环每一轮处理当前队列中的所有格子也就是当前层的所有格子处理完后distance加1。对于每个格子检查上下左右四个方向的邻居如果是海洋且未被访问过就标记为已访问可以直接把值改成1或者用visited数组然后加入队列。队列为空时循环结束返回distance。这里有个细节需要注意distance初始化为-1还是0。因为第一层扩散到的海洋距离应该是1所以我们在处理完第一层之后distance加1变成0再处理第二层变成1……这样最后返回的distance会少1。所以更常见的做法是初始化为-1每处理完一层加1这样第一层处理完distance变成0第二层变成1最后返回的就是最大距离。或者初始化为0每层加1最后返回distance-1。两种写法等价选自己顺手的就行。3.2 代码实现与逐行注释下面是用Python实现的多源BFS版本from collections import deque def maxDistance(grid): n len(grid) queue deque() land_count 0 # 第一步所有陆地入队 for i in range(n): for j in range(n): if grid[i][j] 1: queue.append((i, j)) land_count 1 # 全是陆地或全是海洋 if land_count 0 or land_count n * n: return -1 distance -1 directions [(0, 1), (0, -1), (1, 0), (-1, 0)] # 多源BFS while queue: size len(queue) for _ in range(size): x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx n and 0 ny n and grid[nx][ny] 0: grid[nx][ny] 1 # 标记为已访问 queue.append((nx, ny)) distance 1 return distance这段代码有几个值得说的地方。第一我们直接修改原数组来标记访问把海洋改成陆地这样不需要额外的visited数组空间复杂度从O(N^2)降到O(N^2)但常数更小。第二每一轮while循环处理的是当前层的所有节点用size记录当前队列长度这样能准确控制层数。第三distance在每层处理完后加1初始为-1最终返回的就是最大距离。3.3 复杂度分析与优化空间时间复杂度是O(N^2)因为每个格子最多入队一次、出队一次四个方向的检查是常数时间。空间复杂度也是O(N^2)队列最坏情况下可能存储所有格子。有没有优化空间空间上如果不想修改原数组可以用一个二维布尔数组标记访问但空间复杂度不变。时间上O(N^2)已经是最优了因为至少要把每个格子看一遍。所以这个解法在理论上是无法再优化的。不过实际写代码的时候有一些微小的性能差异。比如用数组模拟队列比用collections.deque在某些语言里更快用方向数组比写四个if更简洁。这些属于工程细节不影响算法本质。4. 从地图分析延伸出去多源BFS的通用套路4.1 腐烂橘子一模一样的思想LeetCode上有一道题叫“腐烂的橘子”题目是网格里0代表空、1代表新鲜橘子、2代表腐烂橘子每分钟腐烂橘子会让上下左右的新鲜橘子腐烂问多少分钟后所有橘子都腐烂如果不可能则返回-1。这道题和地图分析几乎是一个模子刻出来的——所有腐烂橘子是源点同时向外扩散最后扩散到的新鲜橘子就是最后腐烂的层数就是分钟数。代码结构几乎不用改只需要把陆地换成腐烂橘子海洋换成新鲜橘子最后检查是否还有新鲜橘子剩余。如果你能把地图分析写出来腐烂橘子就是五分钟的事。4.2 01矩阵多源BFS求最近距离还有一道题叫“01矩阵”给一个0和1组成的矩阵要求把每个1替换成它到最近0的距离。这道题也是多源BFS的经典应用——把所有0当作源点入队向外扩散每个1第一次被访问到的层数就是它到最近0的距离。这三道题的核心逻辑完全一致区别只在于源点是什么、目标是什么、返回值是什么。掌握一个模板三道题通吃。4.3 多源BFS的通用模板把上面的经验抽象一下多源BFS的通用模板可以写成这样def multi_source_bfs(grid, is_source, is_target): queue deque() # 所有源点入队 for i in range(rows): for j in range(cols): if is_source(grid[i][j]): queue.append((i, j)) distance -1 while queue: size len(queue) for _ in range(size): x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if in_bounds(nx, ny) and is_target(grid[nx][ny]): mark_visited(grid, nx, ny) queue.append((nx, ny)) distance 1 return distance这个模板可以套用到绝大多数网格类多源BFS问题上。你只需要定义什么是源点、什么是目标、怎么标记访问剩下的框架不用动。提示有些题目要求返回具体的距离矩阵而不是最大距离这时候只需要在入队时记录每个格子的距离值最后返回距离矩阵即可。模板的骨架不变。5. 常见问题与排查技巧实录5.1 为什么我的答案总是差1这是新手最容易踩的坑。distance的初始值和加1的时机如果不匹配结果就会差1。我建议的写法是distance初始化为-1每处理完一层加1。这样第一层处理完distance0第二层处理完distance1最后返回的distance就是最大层数。如果你初始化为0每层加1那最后要返回distance-1。还有一种情况是如果队列一开始就是空的全是海洋那while循环根本不执行distance保持-1直接返回-1正好符合题目要求。如果全是陆地我们在入队后就直接判断返回-1了也不会进入循环。5.2 边界条件怎么处理地图分析这道题的边界条件主要有三个全是陆地、全是海洋、只有一个格子。全是陆地和全是海洋都返回-1这个在代码开头判断land_count就能覆盖。只有一个格子的时候如果它是陆地land_count1n*n返回-1如果它是海洋land_count0也返回-1。所以逻辑是自洽的。还有一个隐藏的边界是网格不是正方形的情况。虽然题目说是N×N但实际写代码的时候最好用rows和cols分别表示行列数这样更通用。万一遇到非方阵的变体题代码不用改。5.3 用DFS能不能做理论上可以但非常不优雅。你可以对每个海洋格子做DFS找最近的陆地但复杂度会爆炸。也可以从陆地出发做DFS但DFS不保证最短路径你需要遍历所有路径取最小值复杂度也很高。所以这道题的最佳解法就是BFS不要想太多。5.4 常见问题速查表问题现象可能原因解决方法答案比预期大1distance初始化或加1时机不对初始化为-1每层处理后加1答案比预期小1同上检查是否在循环外多减了1全是海洋时返回0没有提前判断land_count入队后立即判断land_count0全是陆地时返回0没有提前判断land_count判断land_countn*n超时用了暴力BFS改用多源BFS复杂度O(N^2)结果不对但不知道哪错层数控制有问题用size记录当前层节点数注意修改原数组来标记访问虽然省空间但如果题目要求不能修改原数组就需要额外的visited数组。做题前先看清楚要求。6. 实操心得与性能调优经验6.1 队列的选择有讲究在Python里collections.deque的popleft是O(1)的比用list的pop(0)快很多。如果你用list模拟队列pop(0)是O(n)的整体复杂度会退化到O(N^3)。所以一定要用deque。在Java里用ArrayDeque或者LinkedList在C里用std::queue都是类似道理。6.2 方向数组的写法方向数组有两种常见写法一种是[(0,1),(0,-1),(1,0),(-1,0)]另一种是[0,1,0,-1,0]配合循环。前者更直观后者更紧凑。我个人偏好前者因为可读性更好而且调试的时候不容易搞错方向。性能上两者没有区别。6.3 原地修改的利弊原地修改原数组来标记访问好处是省了一个visited数组的空间代码也更简洁。坏处是如果后续还需要用到原数组就得先备份。在做题场景下通常不需要保留原数组所以原地修改是安全的。但在实际工程项目里修改输入参数通常不是好习惯这时候还是老老实实用visited数组。6.4 多源BFS的层数控制技巧层数控制是多源BFS的核心。我见过有人用两个队列交替有人用距离数组有人用size。最简洁的还是用size记录当前层节点数内层for循环处理完当前层所有节点然后distance加1。这个技巧在需要按层处理的BFS题目里通用比如二叉树的层序遍历也是同样的套路。6.5 从这道题能学到什么地图分析这道题表面上是一道算法题实际上教的是思维转换。从“每个海洋找最近陆地”转换成“所有陆地同时扩散”这个转换把O(N^4)降到了O(N^2)。这种“反向思考”和“多源同时处理”的思路在很多优化问题里都能用到。比如多源最短路径、并行任务调度、网络传播模拟等等。我个人在做这道题的时候一开始也是暴力思路提交后超时才发现问题。后来看了讨论区才明白多源BFS的妙处。踩过这个坑之后再遇到类似的网格扩散问题第一反应就是多源BFS省了很多时间。所以如果你现在还在用暴力法建议亲手把多源BFS写一遍感受一下复杂度从O(N^4)降到O(N^2)的爽快。最后分享一个小技巧如果你不确定自己的BFS层数控制对不对可以在每层处理完后打印一下当前层的节点坐标和distance值肉眼观察扩散过程是否符合预期。这个方法在调试任何BFS题目时都很好用比干瞪眼看代码高效得多。