LeetCode 题解工作台
到达最后一个房间的最少时间 II
有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。 给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 堆
答案摘要
我们定义一个二维数组 ，其中 表示从起点到达房间 $(i, j)$ 所需的最少时间。初始时，我们将 数组中的所有元素设为无穷大，然后将起点 $(0, 0)$ 的 值设为 。 我们使用优先队列 存储每一个状态，其中每个状态由三个值 $(d, i, j)$ 组成，表示从起点到达房间 $(i, j)$ 所需的时间为 。初始时，我们将起点 $(0, 0, 0)$ 加入到 中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。
给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为：第一次花费 1 秒，第二次花费 2 秒，第三次花费 1 秒，第四次花费 2 秒……如此 往复 。
请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。
如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。
示例 1：
输入：moveTime = [[0,4],[4,4]]
输出：7
解释：
需要花费的最少时间为 7 秒。
- 在时刻
t == 4，从房间(0, 0)移动到房间(1, 0)，花费 1 秒。 - 在时刻
t == 5，从房间(1, 0)移动到房间(1, 1)，花费 2 秒。
示例 2：
输入：moveTime = [[0,0,0,0],[0,0,0,0]]
输出：6
解释：
需要花费的最少时间为 6 秒。
- 在时刻
t == 0，从房间(0, 0)移动到房间(1, 0)，花费 1 秒。 - 在时刻
t == 1，从房间(1, 0)移动到房间(1, 1)，花费 2 秒。 - 在时刻
t == 3，从房间(1, 1)移动到房间(1, 2)，花费 1 秒。 - 在时刻
t == 4，从房间(1, 2)移动到房间(1, 3)，花费 2 秒。
示例 3：
输入：moveTime = [[0,1],[1,2]]
输出：4
提示：
2 <= n == moveTime.length <= 7502 <= m == moveTime[i].length <= 7500 <= moveTime[i][j] <= 109
解题思路
方法一：Dijkstra 算法
我们定义一个二维数组 ，其中 表示从起点到达房间 所需的最少时间。初始时，我们将 数组中的所有元素设为无穷大，然后将起点 的 值设为 。
我们使用优先队列 存储每一个状态，其中每个状态由三个值 组成，表示从起点到达房间 所需的时间为 。初始时，我们将起点 加入到 中。
在每一次迭代中，我们取出 中的队首元素 ，如果 是终点，那么我们返回 。如果 大于 ，那么我们跳过这个状态。否则，我们枚举 的四个相邻位置 ，如果 在地图内，那么我们计算从 到 的最终时间 ，如果 小于 ，那么我们更新 的值，并将 加入到 中。
时间复杂度 ，空间复杂度 。其中 和 分别是地图的行数和列数。
class Solution:
def minTimeToReach(self, moveTime: List[List[int]]) -> int:
n, m = len(moveTime), len(moveTime[0])
dist = [[inf] * m for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)]
dirs = (-1, 0, 1, 0, -1)
while 1:
d, i, j = heappop(pq)
if i == n - 1 and j == m - 1:
return d
if d > dist[i][j]:
continue
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < m:
t = max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1
if dist[x][y] > t:
dist[x][y] = t
heappush(pq, (t, x, y))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(nm log(nm)) because each room state is processed once in a priority queue. Space complexity is O(nm) to store earliest reachable times for each room and move parity. |
| 空间 | O(nm) |
面试官常问的追问
外企场景- question_mark
Expect you to notice alternating move costs and track state accordingly.
- question_mark
Hinting at using a priority queue suggests shortest path with state propagation.
- question_mark
Ask why naive BFS without parity fails for certain moveTime patterns.
常见陷阱
外企场景- error
Ignoring the odd/even move cost alternation leads to incorrect minimum times.
- error
Failing to wait until moveTime[i][j] for each move can produce invalid paths.
- error
Not tracking separate states for each parity may overestimate or underestimate total time.
进阶变体
外企场景- arrow_right_alt
Allow diagonal moves in addition to cardinal directions, requiring updated state transitions.
- arrow_right_alt
Change move costs to a repeating pattern beyond 1 and 2 seconds, adjusting state tracking.
- arrow_right_alt
Introduce obstacles with infinite moveTime to test unreachable paths.