跳到主要内容

LeetCode 994. 腐烂的橘子

本节目标

从全部腐烂橘子同时开始多源 BFS，按层计算传播分钟数。

这是图的表示与遍历中多源 BFS 的母题：所有初始腐烂橘子在第 0 分钟同时向四个方向传播。

查看 LeetCode 原题

题意与约束​

网格中 0 为空格、1 为新鲜橘子、2 为腐烂橘子。每分钟腐烂橘子会使四邻域新鲜橘子变腐烂。返回所有新鲜橘子腐烂所需最少分钟；若有新鲜橘子无法被感染，返回 -1。没有新鲜橘子时答案为 0。

直接思路与瓶颈​

逐分钟扫描整张网格，把邻近腐烂的橘子标为待腐烂，再统一更新，虽然正确却会重复扫描所有格子。传播持续 k 分钟时复杂度为 O(kmn)，且若原地立即更新又会错误地让本分钟的新橘子继续传播。

图模型与算法推导​

初始化时把所有值为 2 的坐标入队，并计数 fresh。每轮固定当前队列长度，只处理这一层的腐烂橘子；遇到新鲜邻居便立刻改为 2、fresh 减一并入队。整层处理完才分钟加一。队列耗尽后，fresh 为零说明所有橘子都被到达，否则存在被空格隔开的新鲜橘子。

正确性依据​

不变量是：一轮开始时队列恰包含在当前分钟开始前已腐烂、且尚未向外扩张的橘子；fresh 精确等于仍为 1 的格子数。初始化成立。每次感染一个新鲜邻居，立即改写并递减 fresh，使它只会在下一层传播一次。BFS 按层保证新感染橘子的时间是到任一初始源点的最短距离，所以最后一个 fresh 变零的轮数就是最少分钟。

样例执行过程​

以 [[2,1,1],[1,1,0],[0,1,1]] 为例。初始化时 queue = [(0,0)]、fresh = 6、minutes = 0。第 1 分钟感染 (1,0)、(0,1)，下一轮前沿由这两个位置组成，fresh = 4；第 2 分钟感染 (1,1)、(0,2)，fresh = 2。第 3 分钟由当前前沿感染 (2,1)，fresh = 1；第 4 分钟再感染 (2,2)，它入队时 fresh 降为 0。此时 (2,2) 无需再弹出扩张，外层循环因 fresh == 0 停止，minutes = 4，最终返回 4。两种语言的邻居入队顺序可能不同，但每分钟的感染集合一致。

代码实现​

C++17
#include <queue>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = rows == 0 ? 0 : grid[0].size();
        queue<pair<int, int>> queue;
        int fresh = 0;
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == 2) queue.push({row, col});
                if (grid[row][col] == 1) ++fresh;
            }
        }

        int minutes = 0;
        const int directions[5] = {0, 1, 0, -1, 0};
        while (!queue.empty() && fresh > 0) {
            int levelSize = queue.size();
            ++minutes;
            while (levelSize-- > 0) {
                auto [row, col] = queue.front();
                queue.pop();
                for (int direction = 0; direction < 4; ++direction) {
                    int nxtRow = row + directions[direction];
                    int nxtCol = col + directions[direction + 1];
                    if (nxtRow < 0 || nxtRow >= rows || nxtCol < 0 || nxtCol >= cols ||
                        grid[nxtRow][nxtCol] != 1) {
                        continue;
                    }
                    grid[nxtRow][nxtCol] = 2;
                    --fresh;
                    queue.push({nxtRow, nxtCol});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
};

两份源码都在橘子入队时改为 2 并 fresh--。测试覆盖全可腐烂、隔离新鲜橘子、无新鲜橘子和全空网格，并在每个案例前深拷贝输入。

复杂度分析​

每个格至多入队一次，时间复杂度为 O(mn)；队列最坏容纳 O(mn) 个格子，额外空间为 O(mn)。

边界与易错点​

  • 所有初始腐烂橘子都必须在初始化阶段入队，而不是任选一个起点。
  • 当前层长度要在循环开始固定，否则本分钟新感染的橘子会提前传播。
  • 感染时立即改为 2，防止两个腐烂邻居重复入队同一橘子。
  • fresh 初始为零时直接返回 0，不能因为队列非空而增加分钟。

模式迁移​

多源 BFS 可迁移到最近零距离、门到房间的最短距离、火灾扩散和边界侵蚀：先把所有同一时刻的源点入队，再用层次保持统一时间轴；若边有权重，则需改用 Dijkstra 而不是普通队列。