994. 腐烂的橘子 (Medium)
专题归类： 07-图论 LeetCode 链接： https://leetcode.cn/problems/rotting-oranges/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个 m x n 的网格，每个单元格可以有以下三个值之一：
- 值
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
（解释：左下角的橘子永远无法被传染）
示例 3：
输入：grid = [[0,2]]
输出：0
（解释：没有新鲜橘子）
题目详细分析
- 数据范围： m, n 最大均为 10，网格很小（最多 100 个格子），因此不需要担心性能问题，O(m×n) 的算法绰绰有余。
- 输入输出特征： 三类值 0/1/2。返回值为整数分钟数，若无法全腐烂则返回 -1。
- 边界条件：
- 无新鲜橘子 → 返回 0。
- 有新鲜橘子但所有腐烂橘子都无法触及其四周（被 0 包围）→ 返回 -1。
- 一开始就有腐烂橘子，但不是多源（一个或多个都可以）。
- 核心约束： 腐烂只能四方向传播，不能斜向。每分钟所有腐烂橘子同时传播（类似同步 BFS 层序遍历）。
- 隐藏条件： 这是「多源 BFS」的经典模型——与单源 BFS 不同，初始时队列中有多个起点，它们同时向外扩散，BFS 的层数就是传播的分钟数。
小白版直白理解
就像一筐橘子里有几个开始发霉了，霉斑每分钟会扩散到相邻的好橘子。问题是：多久整筐橘子都会烂掉？
注意关键点：所有发霉的橘子 同时 在扩散霉斑，而不是一个一个来。所以我们需要「同时从所有霉点出发，一层一层往外数分钟」。
如果最后发现有些好橘子被空位隔开了，霉斑永远过不去，那就返回 -1 表示不可能全烂。
解题思路
思路一：多源 BFS（推荐）
核心思想： 将所有初始腐烂橘子入队作为 BFS 的起点，然后进行标准的层序遍历。BFS 的层数就等于所需的分钟数。
为什么多源 BFS 可行？因为所有腐烂橘子是「同时」开始腐烂的，多源 BFS 天然模拟了这种同步扩散过程：每一层遍历对应一分钟，所有腐烂橘子在这一分钟同时向四周蔓延。
from collections import deque
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
q = deque()
fresh = 0
# 1. 统计新鲜橘子，腐烂橘子入队
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
dirs = [(1,0), (-1,0), (0,1), (0,-1)]
# 2. BFS 层序遍历
while q and fresh > 0:
minutes += 1
for _ in range(len(q)): # 关键：按层处理
i, j = q.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
fresh -= 1
grid[ni][nj] = 2 # 腐烂
q.append((ni, nj))
return minutes if fresh == 0 else -1复杂度： 时间 O(m×n)，空间 O(m×n)
思路二：BFS 记录时间矩阵
将每个橘子腐烂的时间记录在一个二维数组中，最后取最大值。这种方法不直接依赖层序遍历，而是记录每个节点的”感染时间”。
from collections import deque
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
time = [[-1] * n for _ in range(m)]
q = deque()
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
time[i][j] = 0
q.append((i, j))
dirs = [(1,0), (-1,0), (0,1), (0,-1)]
while q:
i, j = q.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1 and time[ni][nj] == -1:
time[ni][nj] = time[i][j] + 1
q.append((ni, nj))
# 检查是否有新鲜橘子永远无法被感染
max_time = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
if time[i][j] == -1:
return -1
max_time = max(max_time, time[i][j])
return max_time复杂度： 时间 O(m×n)，空间 O(m×n)
易错点
- 新鲜橘子计数与 BFS 结束条件： 在 BFS 过程中如果
fresh == 0，可以提前结束循环，避免不必要的遍历。但注意：最后一分钟的 BFS 结束后，fresh 可能刚好变为 0，此时 minutes 是正确答案。 - 同时腐烂 vs 逐次腐烂： 必须用层序遍历
for _ in range(len(q))来确保同一分钟所有腐烂橘子同步传播。如果不用层序遍历，就变成了每个腐烂橘子依次传播，分钟数会偏大。 - 永远无法腐烂的情况： BFS 结束后仍存在新鲜橘子（fresh > 0），返回 -1。注意检查方式：可以在 BFS 后再次遍历，也可在 BFS 过程中用 fresh 计数器跟踪。
- 空单元格的隔离作用： 值为 0 的空单元格会阻挡腐烂传播，腐烂橘子不能跳过空单元格感染另一侧的新鲜橘子。
- 初始状态无腐烂橘子： 如果初始时没有腐烂橘子但有新鲜橘子，直接返回 -1（不可能腐烂）。
框架提炼
多源 BFS 模板：
def multi_source_bfs(grid, start_value, target_value):
from collections import deque
m, n = len(grid), len(grid[0])
q = deque()
# 1. 将所有源点入队
for i in range(m):
for j in range(n):
if grid[i][j] == start_value:
q.append((i, j))
# 2. 可选：统计目标数量，用于提前终止
target_count = sum(row.count(target_value) for row in grid)
if target_count == 0:
return 0
steps = 0
dirs = [(1,0), (-1,0), (0,1), (0,-1)]
# 3. 层序遍历
while q and target_count > 0:
steps += 1
for _ in range(len(q)):
i, j = q.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == target_value:
target_count -= 1
grid[ni][nj] = start_value # 标记为已访问
q.append((ni, nj))
return steps if target_count == 0 else -1适用场景： 网格中同时从多个源点向外扩散的最短时间/距离问题（如：多个着火点同时燃烧、多水源同时灌溉等）。