3342.到达最后一个房间的最少时间 II

Dijkstra, https://leetcode.cn/problems/find-minimum-time-to-reach-last-room-ii/

有一个地窖，地窖中有 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 <= 750
2 <= m == moveTime[i].length <= 750
0 <= moveTime[i][j] <= 10^9

✅ 思路

需要使用一个 优先队列（最小堆） 来实现 Dijkstra 算法，并且每个状态需要保存三个信息：

time: 当前时间
r, c: 当前所在的坐标
step: 当前是第几步（用于判断下一步是 1 秒还是 2 秒）

并且访问数组应该是一个二维数组 dist[r][c][2]，表示到达 (r, c) 位置时：

如果是从奇数步到达的最短时间；
如果是从偶数步到达的最短时间；

✅ 代码如下：

python

import heapq
from typing import List

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        # dist[i][j][0 or 1]: 到达 (i,j) 时如果是奇数步/偶数步的最早时间
        dist = [[[float('inf')] * 2 for _ in range(m)] for _ in range(n)]
        dist[0][0][0] = 0  # 起点从第0步开始（视为奇数跳）
        # 堆中保存 (当前时间, 行, 列, 步数奇偶性)
        pq = [(0, 0, 0, 0)]

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while pq:
            time, r, c, step = heapq.heappop(pq)

            if r == n - 1 and c == m - 1:
                return time

            if dist[r][c][step % 2] < time: # 优化
                continue

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m:
                    next_step = step + 1
                    cost = 1 if next_step % 2 == 1 else 2
                    arrival_time = max(time, moveTime[nr][nc]) + cost
                    if arrival_time < dist[nr][nc][next_step % 2]:
                        dist[nr][nc][next_step % 2] = arrival_time
                        heapq.heappush(pq, (arrival_time, nr, nc, next_step))

        return -1

if __name__ == "__main__":
    sol = Solution()
    print(sol.minTimeToReach([[0,4],[4,4]]))       # 输出应为 7
    print(sol.minTimeToReach([[0,0,0,0],[0,0,0,0]])) # 输出应为 6
    print(sol.minTimeToReach([[0,1],[1,2]]))       # 输出应为 4

⏱️ 时间复杂度分析：

每个节点最多被访问两次（奇数步和偶数步），因此总共有 n * m * 2 个状态。
使用堆优化的 Dijkstra 算法，总时间复杂度为 O(n * m * log(n * m))，在 n, m <= 750 下是可以通过的。

3342.到达最后一个房间的最少时间 II ​

3342.到达最后一个房间的最少时间 II