LeetCode 题解工作台
腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： 值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们首先遍历一遍整个网格，统计出新鲜橘子的数量，记为 ，并且将所有腐烂的橘子的坐标加入队列 中。 接下来，我们进行广度优先搜索，每一轮搜索，我们将队列中的所有腐烂的橘子向四个方向腐烂新鲜橘子，直到队列为空或者新鲜橘子的数量为 为止。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
在给定的 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
解题思路
方法一：BFS
我们首先遍历一遍整个网格，统计出新鲜橘子的数量，记为 ，并且将所有腐烂的橘子的坐标加入队列 中。
接下来，我们进行广度优先搜索，每一轮搜索，我们将队列中的所有腐烂的橘子向四个方向腐烂新鲜橘子，直到队列为空或者新鲜橘子的数量为 为止。
最后，如果新鲜橘子的数量为 ，则返回当前的轮数，否则返回 。
时间复杂度 ，空间复杂度 。其中 和 分别是网格的行数和列数。
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
cnt = 0
q = deque()
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 2:
q.append((i, j))
elif x == 1:
cnt += 1
ans = 0
dirs = (-1, 0, 1, 0, -1)
while q and cnt:
ans += 1
for _ in range(len(q)):
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
grid[x][y] = 2
q.append((x, y))
cnt -= 1
if cnt == 0:
return ans
return -1 if cnt else 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the grid size and BFS traversal. In the worst case, every cell is visited once, making the time complexity O(m * n), where m is the number of rows and n is the number of columns. The space complexity is also O(m * n) due to the space required to store the grid and BFS queue. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate apply BFS for grid traversal?
- question_mark
Does the candidate handle edge cases like isolated fresh oranges?
- question_mark
Does the candidate consider the multi-source BFS approach for efficiency?
常见陷阱
外企场景- error
Not using BFS correctly and attempting DFS, leading to incorrect time calculations.
- error
Failing to account for edge cases such as no fresh oranges or isolated cells.
- error
Overcomplicating the algorithm with unnecessary data structures or excessive loops.
进阶变体
外企场景- arrow_right_alt
Grid with no empty cells (0) but only fresh (1) and rotten (2) oranges.
- arrow_right_alt
Larger grids requiring more optimized BFS or additional pruning techniques.
- arrow_right_alt
Time complexity analysis with a focus on different grid configurations or larger problem constraints.