腐烂的橘子
Rotting Oranges
本机进度仅保存在当前浏览器
题目描述
在给定的 m x n 网格 grid 中，每个单元格有三个可能的值：0 空格子、1 新鲜橘子、2 腐烂的橘子。每分钟腐烂橘子四周相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数；如果不可能返回 -1。
示例：grid = [[2,1,1],[1,1,0],[0,1,1]]，输出 4。
解题思路
- 这是"多源最短路"：所有腐烂橘子同时开始扩散，用多源 BFS——初始把全部腐烂橘子入队。
- BFS 的层数即扩散的分钟数；每层处理完当前队列全部元素后再进入下一层。
- 新鲜橘子被腐烂时计数递减，结束后仍有剩余则返回 -1；注意无新鲜橘子的边界（返回 0）。
参考实现
查看参考实现Python · 建议先自行作答
from collections import deque
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh += 1
minutes = 0
while queue and fresh:
# 一分钟处理一整层
for _ in range(len(queue)):
i, j = queue.popleft()
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
grid[x][y] = 2
fresh -= 1
queue.append((x, y))
minutes += 1
return minutes if not fresh else -1