腐烂的橘子：
为什么一分钟对应 BFS 的一层

让所有起点，一起出发。

网格里的 0 是空格，1 是新鲜橘子，2 是腐烂橘子。每过一分钟，腐烂会沿上下左右传给相邻的新鲜橘子。要找的是全部新鲜橘子腐烂所需的最少时间；如果有橘子始终无法被感染，答案就是 -1。

这道题的难点集中在两个词：同时、一分钟。所有初始腐烂源从第 0 分钟一起扩散；这一分钟刚腐烂的橘子，要到下一分钟才继续向外传播。

一层一层，看时间往前走。

仓库里的 3 × 3 样例需要 4 分钟。按“下一分钟”，观察这一轮同时改变的格子；也可以换一个情形，看看多个起点和无法到达时的区别。

用队列，划出一分钟的边界。

1. 01

   先把所有初始腐烂橘子入队

   扫描网格时统计 fresh，同时把每个 2 的坐标放进队列。它们都是第 0 层的起点，这样多个源就能一起扩散。

2. 02

   先固定这一层有多少个元素

   进入一轮时记录 size = rear - front，随后只弹出这 size 个元素。处理过程中新增的坐标排在队尾，留到下一轮。这一层处理完，才执行一次 minutes++。

3. 03

   发现新鲜邻居，立即标记再入队

   先把格子从 1 改成 2，再减少 fresh、加入队列。即使两个腐烂源同时碰到这个格子，也只会把它加入一次。

时间在整层结束时增加。

这段代码来自仓库解法，调整了排版，省略扫描初始化与队列函数。完整版本使用两个数组分别保存行、列坐标，每次调用都会重置 front 和 rear。

/* 已统计 fresh，并将所有初始腐烂橘子入队。 */
int minutes = 0;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

while (!empty() && fresh > 0) {
    int size = rear - front;
    for (int i = 0; i < size; i++) {
        int r, c;
        pop(&r, &c);
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 0 || nr >= gridSize ||
                nc < 0 || nc >= gridColSize[nr]) {
                continue;
            }
            if (grid[nr][nc] == 1) {
                grid[nr][nc] = 2;
                fresh--;
                push(nr, nc);
            }
        }
    }
    minutes++;
}
if (fresh == 0) {
    return minutes;
}
return -1;

原题的行、列数均不超过 10。仓库使用固定容量的坐标队列，每个格子最多入队一次；若扩展到更大规模，需要相应调整容量。

原复盘里，留下的四个提醒。

这四条都记录在当时的题目笔记里。把函数调用、队列区间和时间单位写清楚，才能让程序跟上题目的扩散规则。

01 函数调用要有括号

empty 是函数，判断队列是否为空要调用 empty()。只写函数名，没有执行队列为空的判断。

02 半开区间不用多加一

front 指向下一个出队位置，rear 指向下一个入队位置。有效区间是 [front, rear)，长度为 rear - front。

03 一分钟可以腐烂多颗橘子

如果每发现一颗新鲜橘子就增加时间，会把同时发生的扩散错误地排成先后发生。计时应放在一整层处理完之后。

04 检查边界后，再访问格子

某个方向越界就用 continue 跳过，再尝试其他方向。先确认行、列合法，才能读取 grid[nr][nc]。

用几个小网格，检查边界。

把“同时发生”交给队列的一层。

这题留下的一条经验是：当多个起点同时扩散，并且每次移动的代价相同，可以先考虑多源 BFS。初始化决定从哪里一起出发，分层处理决定时间如何流动，入队时标记决定每个格子只被处理一次。

上述复杂度对应仓库中的 C 解法。本页演示额外保留了各分钟状态，以支持回看。