腐烂橘子问题：用多源BFS解最短时间

给你一个m乘n的网格，里面放着三种东西：空格子、新鲜橘子和腐烂橘子。每分钟，每个腐烂橘子会同步感染它上下左右四个方向紧邻的新鲜橘子，让它们也烂掉。现在问你：要让所有橘子都烂掉，最少需要多少分钟？如果永远不可能烂完，就返回-1。

这道题叫“腐烂的橘子”，是很多科技公司面试时的经典算法题。第一次见到它的人，多半会试着一步一步模拟腐烂的过程：每分钟扫一遍整个网格，找到所有当前已经烂掉的橘子，然后把它们相邻的新鲜橘子标记为腐烂，再进入下一分钟，如此循环，直到没有新橘子被感染为止。

这个思路很容易理解，但有一个明显的缺点：每模拟一分钟，就要把整个网格完整遍历一次。假设网格有M行N列，那么在最坏情况下，每个单元格都可能被反复扫描很多遍。具体来说，时间复杂度的上限是O((M×N)²)，也就是把单元格总数再平方一次。对于稍大一点的输入，这个算法就慢得没法用了。

有没有更高效的办法？再仔细想一想腐烂的过程：一开始，网格里可能同时存在多个腐烂的橘子，它们会同时向外扩散，就好像几处火源同时往四周蔓延。如果我们一个一个地处理这些腐烂橘子，等于人为地把并行的过程改成了串行，重复计算了大量无效的步骤。更合理的做法，是把所有这些最初的腐烂橘子当作一组“种子”，在同一时刻开始，同时往外传播。这正好符合一种经典的算法模式——多源广度优先搜索，也就是多源BFS。

在传统的单源BFS中，我们先往队列里放入一个起点，然后一层一层向外扩展，每一层代表一个单位距离。如果把这个距离换成时间，那么每个节点第一次被访问到的时刻，就是从起点到它的最短用时。而多源BFS只是把起点从一个变成多个：在开始时，把所有的腐烂橘子一次性全部丢进队列，记下它们的“时间戳”为0。接下来，BFS自然就会按层级处理：第0分钟处理所有初始腐烂的橘子，第1分钟处理它们感染的第一批新鲜橘子，第2分钟处理第二批，以此类推。每一轮扩展都会把新腐烂的橘子放进队列尾部，等当前层级全部处理完毕，再统一把计时加1，这样就能完美模拟出并行的腐烂过程。

具体到这道题，整个算法可以拆成三步。第一步，遍历网格，做两件事：把所有腐烂的橘子坐标塞进队列，同时数清楚新鲜橘子一共有多少个。之所以要计数，是为了最后判断是不是所有橘子都烂掉了。如果初始时空队列或新鲜橘子数为零，那就不用算了，直接返回0。第二步，开始真正的多源BFS。在队列不为空的情况下，先记下当前队列的大小——这代表“当前这一分钟有待处理的腐烂橘子数量”。然后逐个取出这些烂橘子，检查它们的上下左右四个邻居：如果邻居在网格范围内并且还是新鲜橘子，就把它标记为腐烂，新鲜橘子计数减1，同时把这个新烂掉的坐标加入队列，等待下一分钟处理。每当成功烂掉至少一个新鲜橘子，就说明这一分钟确实发生了传播，计时器增加1。整个过程一直循环，直到队列变空，或者所有新鲜橘子都已腐烂。

第三步很简单：看看新鲜橘子计数是不是减到了零。如果是，返回计时器的值，这就是全部腐烂所需的最短分钟数；如果不是，说明有些新鲜橘子永远接触不到腐烂源，返回-1。

以原文中的例子来演示一下。假设网格长这样：第一行是2、1、1，第二行是1、1、0，第三行是0、1、1。数字2代表烂橘子，1代表好橘子，0是空格。一开始，队列里只有坐标（0,0）这一个腐烂橘子，新鲜橘子一共有6个。

第1分钟：从队列里取出（0,0），检查它的邻居。左边和上边越界，右边（0,1）是新鲜橘子，把它标记为烂橘子，新鲜数减为5，把（0,1）加入队列；下边（1,0）也是新鲜的，同样标记、计数减为4、把（1,0）入队。这一分钟成功烂掉了两个橘子，计时变成1。

第2分钟：队列里现在是（0,1）和（1,0）。先处理（0,1），它上边是越界，下边（1,1）是新鲜橘子，标记、计减、入队，新鲜数变成3。右边（0,2）是新鲜，同样操作，新鲜数变为2。接着处理（1,0），它的四个邻居里，（0,0）已经烂了，（2,0）是空格，右边（1,1）刚才已经标记过，下边越界，没有新感染。这一分钟计时加1，变成2。

第3分钟：队列里有（1,1）和（0,2）。（1,1）的四周：上（0,1）烂了，下（2,1）是新鲜橘子，标记它，新鲜数减为1，入队；左（1,0）烂了，右（1,2）是空格。（0,2）的四周只有左边烂了，其他越界。共感染一个新橘子，计时变3。

第4分钟：队列里只有（2,1）。它的邻居下边越界，左边空格，右边（2,2）是新鲜橘子，标记后新鲜数归零。计时再加1变成4，新鲜橘子数为0，循环结束。最后返回4，这就是答案。

这个算法的巧妙之处，在于它利用了BFS天然按层级遍历的特性，直接把“分钟”和“层级”一一对应起来。所有腐烂橘子在同一分钟里作用的邻居，都在BFS的同一层中被发现并标记。而一个新鲜橘子第一次被某个腐烂邻居感染的时间，恰好就是它被加入队列时所在的层数，也即最短的腐烂用时。后续即使有更晚的传播路径到达同一个橘子，我们也不会再处理，因为它在更早的分钟就已经烂掉了。

从复杂度来看，这种方法把每个单元格最多访问一次，时间上限降到O(M×N)；空间上，最差情况下队列里可能同时塞满所有单元格，所以也是O(M×N)。相比于暴力模拟的平方级复杂度，提升是质的飞跃。

这道题的价值，还不仅仅在于解决腐烂橘子本身。一旦认出了“多处源头同时向外扩散、求最少时间或最短距离”的模式，你就拿到了多源BFS的钥匙。看到疫情传播、山火蔓延、网络信息扩散这类场景，只要题目中出现“多起点同步扩散”的意味，就可以直接把这个思路迁移过去：把所有初始源一次性入队，然后BFS逐层处理，每个节点的首次访问时间即为所求。

下次再碰上类似的网格感染问题，就不必逐分钟扫全局，而是直接让算法像真的传播那样，由内而外同步推进。