华为 OD 训练营 · 题解精讲
LC994. 腐烂的橘子
LC994. 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： 值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1： R1HCbHvhQoyKzKxzTogcK4s4nCb.png
输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4 示例 2： 输入：grid = [[2,1,1],[0,1,1],[1,0,1]] 输出：-1 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。 示例 3： 输入：grid = [[0,2]] 输出：0 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
题目解析
解题思路
本题是一个典型的多源 BFS 问题。每分钟所有已腐烂的橘子会同时感染其上下左右的新鲜橘子，这相当于 BFS 中同一层的节点同时向外扩展一层。初始时所有腐烂橘子都是 BFS 的起点（多源），BFS 的层数就是所需分钟数。
关键点：
- 用队列存储当前所有腐烂橘子的坐标，BFS 逐层扩展
- 用
checkList标记已访问过的位置，防止重复处理 - 统计新鲜橘子总数，每感染一个就减 1，最后判断是否全部腐烂
关键步骤
1. 初始化：遍历网格，将所有腐烂橘子入队，统计新鲜橘子数量 fresh_num。若 fresh_num == 0 直接返回 0。 2. BFS 分层遍历：
- 每次取出当前队列所有元素（同一层），
level加 1 - 对每个出队元素，检查四个方向的新鲜橘子，若未访问且是新鲜橘子，则入队、标记、
fresh_num减 1
3. 结果判断：BFS 结束后，若 fresh_num > 0 返回 -1，否则返回 level - 1（因为初始腐烂橘子不计时）。
BFS 分层过程示意（以 2x2 网格为例）：
初始：2 1 第1分钟：2 2 第2分钟：2 2
1 1 1 2 2 2
level=0 level=1 level=2复杂度分析
- 时间复杂度：O(m × n)，每个格子最多入队一次，遍历网格一次。
- 空间复杂度：O(m × n)，队列和
checkList数组各需 O(m × n) 空间。
参考代码
# 题目：LC994. 腐烂的橘子
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：多源BFS
# 代码看不懂的地方，请直接在群上提问
D = [(0,1), (1,0), (-1,0), (0,-1)]
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
# 初始化答案变量、新鲜橘子数量、网格长宽
level, fresh_num, x, y = 0, 0, len(grid), len(grid[0])
# 初始化队列，维护BFS过程
q = deque()
# 初始化二维列表，用于BFS过程中的检查
checkList = [[0] * y for _ in range(x)]
# 第一次遍历整个二维网格，找到所有初始腐烂的橘子，统计新鲜橘子的个数
for i in range(x):
for j in range(y):
# 找到初始腐烂的橘子
if grid[i][j] == 2:
# 将腐烂的橘子放入队列中
q.append((i, j))
# 同时修改二维检查列表的对应元素为1
checkList[i][j] = 1
# 找到初始新鲜的橘子
elif grid[i][j] == 1:
# 统计新鲜橘子的数目
fresh_num += 1
# 若新鲜橘子数量为0，则直接返回0
if fresh_num == 0:
return 0
# 进行BFS搜索的循环，套用BFS万能模板
while len(q) > 0:
# 获得当前队列长度，为当前层搜索的个数
qSize = len(q)
# 搜索层数+1
level += 1
# 循环qSize次，出队qSize次
for _ in range(qSize):
# 出队
i, j = q.popleft()
# 考虑上下左右四个方向的其他位置
for dx, dy in D:
nxt_i, nxt_j = i+dx, j+dy
# 满足三个条件
if 0 <= nxt_i < x and 0 <= nxt_j < y and checkList[nxt_i][nxt_j] == 0 and grid[nxt_i][nxt_j] == 1:
# 新鲜橘子入队，标记检查，新鲜橘子数目-1
q.append((nxt_i, nxt_j))
checkList[nxt_i][nxt_j] = 1
fresh_num -= 1
# 若BFS结束，仍存在新鲜橘子，说明有些橘子无法腐烂，返回-1
# 否则返回level-1，为腐烂所有新鲜橘子所需的时间
return -1 if fresh_num > 0 else level-1