难度: Medium
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
0 代表空单元格；1 代表新鲜橘子；2 代表腐烂的橘子。每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -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 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]] 输出：0 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j] 仅为 0、1 或 2运行时间: 18 ms
内存: 16.1 MB
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
M = len(grid)
N = len(grid[0])
queue = []
count = 0
for r in range(M):
for c in range(N):
if grid[r][c] == 1:
count += 1
elif grid[r][c] == 2:
queue.append((r, c))
def valid(x, y):
return 0<=x<M and 0<=y<N
round = 0 # round 表示腐烂的轮数，或者分钟数
while count > 0 and len(queue) > 0:
round += 1
n = len(queue)
for i in range(n):
r, c = queue.pop(0)
for [x, y] in [[0,1], [0,-1], [1,0], [-1,0]]:
new_x, new_y = r+x, c+y
if valid(new_x, new_y) and grid[new_x][new_y] == 1:
grid[new_x][new_y] = 2
count -= 1
queue.append((new_x, new_y))
if count > 0:
return -1
else:
return round
This solution uses the Breadth-First Search (BFS) algorithm to simulate the rotting process of oranges. It starts by identifying all initially rotten oranges and counting fresh oranges. It enqueues all rotten oranges' positions. Using BFS, it iteratively infects fresh oranges adjacent to rotten ones each minute, marking them rotten and decreasing the fresh count. This continues until no fresh oranges are left or there are no more adjacent fresh oranges to infect, at which point the process stops. If any fresh oranges remain unreachable, it returns -1, otherwise, it returns the number of minutes passed.
时间复杂度: O(M * N)
空间复杂度: O(M * N)
# Class definition for the rotting oranges problem
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
M = len(grid) # Number of rows in the grid
N = len(grid[0]) # Number of columns in the grid
queue = [] # Queue to store positions of rotten oranges
count = 0 # Count of fresh oranges
for r in range(M):
for c in range(N):
if grid[r][c] == 1: # Count fresh oranges
count += 1
elif grid[r][c] == 2: # Initialize queue with all rotten oranges
queue.append((r, c))
def valid(x, y):
return 0<=x<M and 0<=y<N # Helper function to check boundaries
round = 0 # round represents the number of minutes passed
while count > 0 and len(queue) > 0: # While there are fresh oranges and rotten ones to process
round += 1
n = len(queue) # Number of oranges to process this round
for i in range(n):
r, c = queue.pop(0) # Pop the first rotten orange from the queue
for [x, y] in [[0,1], [0,-1], [1,0], [-1,0]]: # Check all 4 adjacent cells
new_x, new_y = r+x, c+y
if valid(new_x, new_y) and grid[new_x][new_y] == 1: # If adjacent cell is fresh
grid[new_x][new_y] = 2 # It rots
count -= 1 # Decrease count of fresh oranges
queue.append((new_x, new_y)) # Enqueue the newly rotten orange
if count > 0: # If there are still fresh oranges left
return -1 # It's impossible to rot all oranges
else:
return round # Return the total minutes required
BFS 是模拟橘子腐烂过程的理想选择，因为它可以确保以最快的速度同时向所有方向传播。这种方式确保每一分钟内所有已腐烂的橘子都能同时影响其相邻的新鲜橘子。相比之下，DFS 会沿一个可能的路径深入，可能导致某些橘子比其他路径上的橘子更晚腐烂，这不符合橘子腐烂的自然过程，即橘子的腐烂应该是同时发生的。
算法中使用了一个名为 `valid` 的辅助函数来检查一个位置是否在网格内。这个函数检查给定的坐标 (x, y) 是否满足 0 <= x < M 和 0 <= y < N，其中 M 和 N 分别是网格的行数和列数。只有当这些条件都满足时，才会对该位置进行处理，从而确保算法不会尝试访问网格边界之外的位置。
使用队列存储即将腐烂的橘子的位置是为了按照腐烂发生的顺序处理每个橘子。在BFS中，队列首先初始化为所有已经腐烂的橘子的位置。每一轮中，算法从队列中移除当前腐烂的橘子，并将其周围的新鲜橘子标记为腐烂并加入队列中。这样可以保证每一分钟所有可腐烂的橘子都被处理，从而模拟出腐烂的扩散过程。
在BFS执行过程中，如果某一轮结束时没有新的橘子腐烂（即队列为空），算法会立即终止。这是因为没有更多的腐烂橘子可以传播腐烂，所有剩余的新鲜橘子都不可达，因此进一步的搜索是无效的。算法会返回-1表示不可能腐烂所有橘子。