腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可能是：
0：空单元格1：新鲜橘子2：腐烂的橘子
每分钟，腐烂的橘子会使周围四个方向上相邻的新鲜橘子腐烂。
返回直到没有新鲜橘子为止所必须经过的最小分钟数。如果不可能让所有新鲜橘子腐烂，返回 -1。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]]
输出：0
解释：0 分钟时已经没有新鲜橘子了，所以答案就是 0。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]仅为0、1或2
多源 BFS：
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int freshCount = 0;
queue<pair<int, int>> rotten;
for (int row = 0; row < m; ++row)
{
for (int col = 0; col < n; ++col)
{
if (grid[row][col] == 1)
{
++freshCount;
}
else if (grid[row][col] == 2)
{
rotten.push({row, col});
}
}
}
if (freshCount == 0)
{
return 0;
}
int minutes = 0;
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!rotten.empty())
{
int size = rotten.size();
bool hasNewRotten = false;
for (int i = 0; i < size; ++i)
{
auto [row, col] = rotten.front();
rotten.pop();
for (const auto& direction : directions)
{
int nextRow = row + direction[0];
int nextCol = col + direction[1];
if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n)
{
continue;
}
if (grid[nextRow][nextCol] != 1)
{
continue;
}
grid[nextRow][nextCol] = 2;
--freshCount;
hasNewRotten = true;
rotten.push({nextRow, nextCol});
}
}
if (hasNewRotten)
{
++minutes;
}
}
return freshCount == 0 ? minutes : -1;
}
};
核心思想
将腐烂过程看成按层扩散
腐烂会在每一分钟同时发生：
- 第
0分钟：网格中原本腐烂的橘子已经腐烂。 - 第
1分钟：距离初始腐烂橘子一步的新鲜橘子腐烂。 - 第
2分钟：距离初始腐烂橘子两步的新鲜橘子腐烂。
这正好符合 BFS 的按层遍历特征。
因此，应该把所有初始腐烂橘子同时加入队列，作为 BFS 的多个起点，而不是从某一个腐烂橘子单独开始搜索。
为什么是多源 BFS
如果网格中有多个腐烂橘子，它们会同时向外扩散。
某个新鲜橘子腐烂所需的时间，等于它到最近的初始腐烂橘子的最短四方向距离。
BFS 天然按照距离从小到大访问位置，所以多源 BFS 第一次腐烂某个橘子的时刻，就是它能够腐烂的最早时刻。
队列中存什么
队列中保存当前已经腐烂、并且还需要继续向外扩散的橘子坐标。
每一轮循环开始时，队列中已有的元素都属于同一分钟会向外扩散的腐烂橘子。
因此先记录当前队列大小 size，只处理这 size 个元素，就能保证一轮循环对应一分钟的传播范围。
计时方式
代码使用变量 minutes 记录已经发生了多少分钟的有效腐烂传播。
每一层 BFS 处理完后，只有当这一层真的让至少一个新鲜橘子腐烂时，才让 minutes 加一：
if (hasNewRotten)
{
++minutes;
}
这样可以避免最后一层腐烂橘子已经无法继续感染新鲜橘子时，额外多计算一分钟。
如果一开始就没有新鲜橘子，直接返回 0，因为不需要等待任何腐烂过程。
为什么需要统计新鲜橘子数量
变量 freshCount 表示当前还没有腐烂的新鲜橘子数量。
每当一个新鲜橘子被腐烂，就将它改成 2，并令 freshCount 减一。
BFS 结束后：
- 如果
freshCount == 0，说明所有新鲜橘子都已经腐烂，返回经过的分钟数。 - 如果
freshCount > 0，说明仍有新鲜橘子无法被任何腐烂橘子到达，返回-1。
正确性证明
结论 1：BFS 可以模拟每分钟同时扩散
算法一开始将所有初始腐烂橘子加入队列，它们都属于第 0 分钟的腐烂源。
每轮 BFS 只处理当前队列中已有的橘子，并把新腐烂的橘子加入队列尾部，留到下一轮再继续扩散。
因此第 t 轮中新腐烂的橘子，恰好是在第 t 分钟被腐烂的橘子，算法与题目的同步扩散过程一致。
结论 2：每个橘子第一次腐烂的时间最小
BFS 按照从初始腐烂橘子的四方向距离由近到远扩展。
当某个新鲜橘子第一次被访问时，说明已经找到一条从某个初始腐烂橘子到它的最短路径。若存在更早腐烂它的方式，那么它会在更早的 BFS 层中被访问，与第一次访问发生在当前层矛盾。
因此算法记录的腐烂时间是该橘子可能腐烂的最早时间。
结论 3：返回 -1 当且仅当存在无法腐烂的新鲜橘子
BFS 会沿四方向访问所有能够从初始腐烂橘子到达的新鲜橘子，并将它们腐烂。
如果 BFS 结束后仍有 freshCount > 0，这些新鲜橘子无法通过四方向路径连接到任何初始腐烂橘子，所以不可能腐烂。
反之，如果所有新鲜橘子都能被腐烂，BFS 一定会访问并腐烂它们，最终 freshCount == 0。
综上，算法能够正确返回使所有橘子腐烂所需的最小分钟数；若无法全部腐烂，则正确返回 -1。
示例分析
以 grid = [[2,1,1],[1,1,0],[0,1,1]] 为例：
第 0 分钟：初始腐烂橘子在 (0,0)
第 1 分钟：(0,1)、(1,0) 腐烂
第 2 分钟：(0,2)、(1,1) 腐烂
第 3 分钟：(2,1) 腐烂
第 4 分钟：(2,2) 腐烂
所有新鲜橘子都腐烂后，共经过 4 分钟。
复杂度分析
- 时间复杂度：
O(mn)。每个格子最多入队一次，并且每次只检查四个方向。 - 空间复杂度：
O(mn)。最坏情况下，队列中可能存放所有格子的坐标。
边界情况
- 初始时没有新鲜橘子：直接返回
0。 - 没有腐烂橘子但存在新鲜橘子：BFS 无法启动，最终返回
-1。 - 新鲜橘子被空单元格隔开：无法通过四方向传播到达，最终返回
-1。 - 网格只有一行或一列：边界判断保证只访问合法的相邻位置。