994. 腐烂的橘子

题目描述

网格里 2=烂、1=好、0=空。每分钟烂橘子让上下左右相邻的好橘子变烂。几分钟后全烂？

思路解析

普通 BFS 从一个点出发；这里把所有初始烂橘子一次性放进队列，同时向四周扩散。每扩散一整层 = 过去一分钟。

第 0 分钟：初始只有左上角(0,0)是烂的(橙)，它先进队列。绿色是好橘子，灰色是空格。

开始前先扫一遍：统计好橘子数 fresh=6，并把所有烂橘子(这里 1 个)放进队列。fresh 用来最后判断是否全烂。

第 1 分钟：第 1 分钟：(0,0) 把右、下两个好邻居 (0,1)、(1,0) 传染变烂(高亮)，它们进入下一层队列。

第 2 分钟：第 2 分钟：上一层的烂橘子再传染各自的好邻居——(0,2) 和 (1,1) 变烂。

第 3 分钟：第 3 分钟：(1,1) 把下面的 (2,1) 传染变烂。(中间的 0 是空格，挡住了路)

第 4 分钟：第 4 分钟：(2,1) 传染最后的 (2,2)。全部变烂，答案 = 4 分钟。

队列空后检查 fresh：这里减到 0，返回分钟数 4。若还有好橘子被空格隔绝(fresh>0)，则返回 -1。

以后你遇到「同时从多处扩散、求最短时间/距离」的题，就用多源 BFS：01 矩阵、地图分析都是它。

参考代码（Python）

1q = deque()
2for 每个格子:
3    if 是烂橘子: q.append((i,j))   # 所有烂橘子一起入队
4    elif 是好橘子: fresh += 1
5while q and fresh > 0:
6    level += 1                     # 过去一分钟
7    for _ in range(len(q)):        # 只处理class="cl-str">"这一层"
8        i,j = q.popleft()
9        for 四个方向的好邻居:
10            变烂; fresh -= 1; q.append(邻居)
11return level if fresh == 0 else -1

复杂度分析

• 时间复杂度：O(m×n) —— 每格进出队一次
• 空间复杂度：O(m×n) —— 队列最多装一层

套路模板

记住骨架：所有起点一次性入队、for range(len(q)) 锁层、每层 +1。01 矩阵、地图分析都是把多个源同时入队，和单源 BFS 只差「起点个数」。

1# 「同时从多个源扩散、求最短时间/距离」都套
2q = deque(所有起点); seen = set(所有起点)
3level = 0
4while q:
5    for _ in range(len(q)):        # 锁定class="cl-str">"这一层"
6        x = q.popleft()
7        for y in 邻居(x):
8            if y not in seen: seen.add(y); q.append(y)
9    level += 1                     # 一层 = 一个时间单位

易错点

• ❌ 只把一个烂橘子入队 → ✅ 初始所有烂橘子都入队（它们是同时开始腐烂的）
• ❌ 不按层、直接数步数 → ✅ for _ in range(len(q)) 锁定当前层（否则分不清「第几分钟」）
• ❌ 忘了判断剩余好橘子 → ✅ 最后 fresh>0 返回 -1（有的好橘子被空格隔绝，永远烂不了）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。