Rotting Oranges
你会得到一个网格，它是由等长行组成的列表。每个单元格的值为 0（空）、1（新鲜橘子）或 2（腐烂橘子）。每过一分钟，与腐烂橘子上下左右相邻的新鲜橘子都会变腐烂。返回直到没有新鲜橘子所需的分钟数；如果有些新鲜橘子永远不会腐烂，则返回 -1。如果网格一开始就没有新鲜橘子，则需要 0 分钟。
函数
- gridinteger-2d-array
- 网格，每行一个由 0、1 和 2 组成的列表
- 返回值integer
- 直到没有新鲜橙子所需的分钟数，如果永远不会发生，则为 -1
约束条件
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- 每一行的长度都相同。
- 每个
grid[i][j]都是0、1或2。
示例
- 输入
- grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
- 输出
- 6
- 解释
- 单元格用（行，列）表示。腐烂过程沿着从 (0,0) 出发的唯一路径进行，并在第 5 分钟到达 (2,3)。(1,3) 处的橘子只与 (2,3) 相邻，因此最后腐烂，在第 6 分钟。
- 输入
- grid = [[2, 1, 0], [0, 0, 1]]
- 输出
- -1
- 解释
- 位于 (1,2) 的橙子上方和左侧都是空格子，下方和右侧则是网格边缘。没有腐烂的橙子能到达它，所以答案是 -1。
- 输入
- grid = [[0, 2, 0, 2]]
- 输出
- 0
- 解释
- 开始时没有新鲜橙子，所以不需要经过任何时间，答案是 0。
进阶
假设每个新鲜橙子在相邻的橙子腐烂后，都需要各自不同的分钟数才会腐烂。那么你该如何找出全部腐烂所需的时间？
提示
逐个打开提示，每个都会多透露一点。
把腐烂想象成一波波扩散。第 3 分钟时，哪些橙子会腐烂？只有紧挨着第 2 分钟时变腐烂的橙子的那些新鲜橙子。
从每个腐烂的橙子同时开始进行一次广度优先搜索：在搜索开始前，把它们全部放入队列。这样，队列中始终保存着腐烂区域的边缘。
每次处理一层队列：读取该层的大小，取出相应数量的单元格，每层计 1 分钟。先统计新鲜橙子的数量，等它们腐烂时就减少计数。计数达到 0 时立即停止；如果队列先空了，就返回 -1。
题解
腐烂会从每个腐烂的橘子同时开始扩散，每分钟传播一个格子，所以答案是一个距离：最远的新鲜橘子到离它最近的腐烂橘子有多远。当每个腐烂的橘子都从一开始就进入队列，并且队列的每一层代表一分钟时，广度优先搜索就能测出这个距离。
逐分钟模拟
结果正确，但无法在最大的测试中运行完毕
思路
每分钟扫描整个网格，列出所有与腐烂橘子相邻的新鲜橘子。然后让它们全部腐烂，并将时间计数加 1。当扫描后发现没有橘子需要腐烂时就停止；如果还有新鲜橘子，返回 -1。
先列出，再让它们腐烂。如果你在扫描过程中途让一个橘子腐烂，那么同一轮扫描中稍后检查到的格子会把它视为腐烂橘子，这样腐烂状态就会在一分钟内越过多个格子。
每分钟都要扫描 rows × cols 个格子，而所需分钟数可能接近格子总数：在 150 × 150 的网格上，一条蜿蜒的路径需要 11,324 分钟，大约要检查 2.5 × 10^8 个格子。
算法
- 将 minutes 设为 0。
- 扫描网格，列出每个相邻位置有腐烂橙子的鲜橙。
- 如果列表为空，就停止。否则，将列表中的所有橙子变为腐烂状态，minutes 加 1，然后再次扫描。
- 如果还有鲜橙，就返回 -1，否则返回 minutes。
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
minutes = 0
while True:
# Find every fresh orange that touches a rotten one right now.
to_rot = []
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
to_rot.append((r, c))
break
if not to_rot:
break
# Rot them only after the scan, so the rot moves one step a minute.
for r, c in to_rot:
grid[r][c] = 2
minutes += 1
for row in grid:
if 1 in row:
return -1
return minutes按层进行多源 BFS
思路
在第 t+1 分钟可能腐烂的橘子，只有第 t 分钟腐烂的橘子旁边的新鲜橘子，所以只需把这些橘子放入队列。先把第 0 分钟已经腐烂的所有橘子放入队列。新鲜橘子会在与最近腐烂橘子的距离所对应的分钟腐烂，而以所有源点为起点的广度优先搜索，会先从距离每个单元格最近的源点到达该单元格。
按层处理。在每分钟开始时，队列中存放的是上一分钟腐烂的橘子；从队首取出恰好这么多个橘子，让它们相邻的新鲜橘子腐烂，并将这些橘子加入队尾。剩下的就是下一层边界。
先统计新鲜橘子的数量，当数量变为 0 时停止；如果最后一层没有让任何橘子腐烂，也停止。每个单元格最多进入队列一次：O(rows × cols)。
算法
- 将所有腐烂的橘子放入队列，并统计新鲜橘子的数量。
- 将 minutes 设为 0。当队列不为空且还有新鲜橘子时，将 minutes 加 1，并记下队列的大小 k。
- 从队首取出 k 个橘子。对于网格内每个新鲜的相邻橘子，将其标记为腐烂，新鲜橘子的数量减 1，再将它放到队尾。
- 循环结束后，如果新鲜橘子的数量为 0，则返回 minutes；否则返回 -1。
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Every orange that is rotten at minute 0 starts in the queue.
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh > 0:
minutes += 1
# The queue holds exactly the oranges that went rotten last minute.
# Rot their fresh neighbours; those become the next minute's queue.
for _ in range(len(queue)):
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1
易错点和边界情况
- 最后一层也要计入 1 分钟。如果循环一直运行到队列为空，最后一轮不会让任何橘子腐烂，却仍会增加 1。没有新鲜橘子时就停止。
- 依次从每个腐烂的橘子开始搜索。第一次搜索会按照自己的计时，把它能到达的所有橘子都占为己有：
[[2, 1, 1, 1, 1, 1, 1, 2]]，这样会得到 6 分钟，而不是 3 分钟。 - 因为没有腐烂的橘子就返回 -1。如果也没有新鲜橘子，就不需要做任何事：
[[0]]返回 0。 - 橘子离开队列时才将其标记为腐烂，而不是进入队列时。这样，挨着两个腐烂橘子的橘子就会入队两次，新鲜橘子的数量会降到零以下。
常见问题3
腐烂的橘子的时间复杂度是多少？
使用广度优先搜索的时间复杂度为 O(rows × cols)：第一次扫描会读取每个单元格一次，每个橙色单元格最多入队一次，并检查四个相邻单元格。最坏情况下，队列占用 O(rows × cols) 的空间。
为什么在腐烂的橘子问题中使用 BFS，而不使用 DFS？
广度优先搜索会按单元格与源点之间的距离依次访问它们，在这里，距离表示时间：第 k 层是指在第 k 分钟腐烂的橘子。深度优先搜索可能会先绕很远的路到达某个单元格，之后每次发现更短的路径时，都必须重新访问它。
你能在不更改网格的情况下解决 Rotting Oranges 吗？
是的。单独维护一个已访问数组，并检查它，而不是在网格中写入 2。这样会额外占用 O(rows × cols) 的内存，不过队列本来也可能需要这些内存，而且调用方的网格会保持原样。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def orangesRotting(grid):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
预期输出
6