LeetCode 题解工作台
逃离火灾
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一： 0 表示草地。 1 表示着火的格子。 2 表示一座墙，你跟火都不能通过这个格子。 一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n -…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
我们注意到，如果一个停留时间 满足条件，那么所有小于 的时间也都满足条件。因此我们可以考虑使用二分查找的方法找到最大的满足条件的时间。 我们定义二分查找的左边界 ，右边界 $r = m \times n$。每一次二分查找，我们都将 和 的中点 作为当前的停留时间，判断是否满足条件。如果满足条件，那么我们将 更新为 ，否则我们将 更新为 。最后，如果 $l = m \times n$，…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：
0表示草地。1表示着火的格子。2表示一座墙，你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。
注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。
如果两个格子有共同边，那么它们为 相邻 格子。
示例 1：
输入：grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]] 输出：3 解释：上图展示了你在初始位置停留 3 分钟后的情形。 你仍然可以安全到达安全屋。 停留超过 3 分钟会让你无法安全到达安全屋。
示例 2：
输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]] 输出：-1 解释：上图展示了你马上开始朝安全屋移动的情形。 火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。 所以返回 -1 。
示例 3：
输入：grid = [[0,0,0],[2,2,0],[1,2,0]] 输出：1000000000 解释：上图展示了初始网格图。 注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。 所以返回 109 。
提示：
m == grid.lengthn == grid[i].length2 <= m, n <= 3004 <= m * n <= 2 * 104grid[i][j]是0，1或者2。grid[0][0] == grid[m - 1][n - 1] == 0
解题思路
方法一：二分查找 + BFS
我们注意到，如果一个停留时间 满足条件，那么所有小于 的时间也都满足条件。因此我们可以考虑使用二分查找的方法找到最大的满足条件的时间。
我们定义二分查找的左边界 ，右边界 。每一次二分查找，我们都将 和 的中点 作为当前的停留时间，判断是否满足条件。如果满足条件，那么我们将 更新为 ，否则我们将 更新为 。最后，如果 ，那么说明不存在满足条件的停留时间，我们返回 ，否则我们返回 。
问题的关键转化为如何判断一个停留时间 是否满足条件。我们可以使用广度优先搜索的方法，在 时间内，模拟火的蔓延过程。如果停留 时间后，火蔓延到了起点位置，那么说明不满足条件，提前返回。否则，我们这时候再使用广度优先搜索，每一次从当前位置向四个方向进行搜索，每一轮结束后，我们还需要将火向四个方向蔓延一次。如果在这个过程中，我们找到了一条从起点到终点的路径，那么说明满足条件。
时间复杂度 ，空间复杂度 。其中 和 分别为网格的行数和列数。
class Solution:
def maximumMinutes(self, grid: List[List[int]]) -> int:
def spread(q: Deque[int]) -> Deque[int]:
nq = deque()
while 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 not fire[x][y] and grid[x][y] == 0:
fire[x][y] = True
nq.append((x, y))
return nq
def check(t: int) -> bool:
for i in range(m):
for j in range(n):
fire[i][j] = False
q1 = deque()
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 1:
fire[i][j] = True
q1.append((i, j))
while t and q1:
q1 = spread(q1)
t -= 1
if fire[0][0]:
return False
q2 = deque([(0, 0)])
vis = [[False] * n for _ in range(m)]
vis[0][0] = True
while q2:
for _ in range(len(q2)):
i, j = q2.popleft()
if fire[i][j]:
continue
for a, b in pairwise(dirs):
x, y = i + a, j + b
if (
0 <= x < m
and 0 <= y < n
and not vis[x][y]
and not fire[x][y]
and grid[x][y] == 0
):
if x == m - 1 and y == n - 1:
return True
vis[x][y] = True
q2.append((x, y))
q1 = spread(q1)
return False
m, n = len(grid), len(grid[0])
l, r = -1, m * n
dirs = (-1, 0, 1, 0, -1)
fire = [[False] * n for _ in range(m)]
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return int(1e9) if l == m * n else l
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a candidate who can handle the combination of binary search and BFS effectively.
- question_mark
Assess if the candidate understands how fire spread impacts pathfinding and timing.
- question_mark
Evaluate the candidate's approach to handling large grids and efficient time management.
常见陷阱
外企场景- error
Misunderstanding how fire spreads and when it reaches each cell, leading to incorrect time estimations.
- error
Failing to account for edge cases where the fire immediately blocks the path to the safehouse.
- error
Not optimizing the solution with binary search, leading to unnecessary time complexity.
进阶变体
外企场景- arrow_right_alt
Consider grids with more complex fire spread patterns, including diagonal spreads or multiple fire sources.
- arrow_right_alt
Change the problem’s constraints to allow multiple safehouses and examine how that impacts the solution.
- arrow_right_alt
Alter the fire spread rules, such as allowing the fire to spread slower or faster, and analyze the effect on the algorithm.