点击获取AI摘要

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

有一个地窖，地窖中有 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⁹

问题分析

有一个 $\times m$ 的房间网格，起点是 $(0,0)$ ，终点是 $(n-1,m-1)$ 。
你在 时刻 0 从起点出发，每次只能向上、下、左、右走一步。
第 1 步花费 1 秒，第 2 步花费 2 秒，第 3 步花费 1 秒，第 4 步花费 2 秒，以此类推（奇数步 1 秒，偶数步 2 秒）。
另外，每个房间 $(i,j)$ 有一个 开放时间 moveTime[i][j]，表示 在此时刻以后才能进入该房间。如果你走到某房间的时刻还没到它的开放时间，就要在外面等到 moveTime[i][j] 才能进去。

目标：求从 $(0,0)$ 到 $(n-1,m-1)$ 的最少总耗时。

算法思路

普通最短路：
- 如果每次移动的耗时固定（比如都 1 秒），经典做法是 BFS；
- 如果耗时不固定且无等待，则可以用 Dijkstra（或 SPFA）。
本题特点：
- 每一步的耗时依赖于「已经走过的步数是奇数还是偶数」。
- 还要考虑「到达时间 < 房间开放时间」时的等待。
这两点都会影响「从一个节点走到另一个节点的实际耗时」，而且这个耗时不是固定的常数。
带状态建模：
- 我们把“走过步数的奇偶”当成状态之一。
- 状态 $(i,j,p)$ 表示「当前位置在 $(i,j)$ 且已经走了 $k$ 步，且 $p = k \bmod 2$ 」（ $p=0$ 代表下一步是第 $k+1$ 步且为奇数； $p=1$ 代表下一步为偶数）。
状态转移：
- 从 $(i,j,p)$ 可以去相邻的 $(ni,nj)$ ，新的奇偶状态是 $np = 1 - p$ 。
  
  计算本步原始移动耗时：
  
  $w = \begin{cases} 1, & \text{若 }np = 1\ (\text{下一步是奇数步});\\ 2, & \text{若 }np = 0\ (\text{下一步是偶数步}). \end{cases}$
- 等待时机：
  - 你要在房间 $(ni,nj)$ 开放后才能开始这一步移动，
    所以先算
    
    $t_{\text{start}} = \max\bigl(t_{\rm cur},\,\text{moveTime}[ni][nj]\bigr).$
  - 然后再花费 $w$ 秒到达：
    
    $t_{\rm new} = t_{\text{start}} + w.$
使用 Dijkstra
- 定义 dist[i][j][p] 为达到状态 $(i,j,p)$ 的最小时间。
- 初始只有 dist[0][0][0] = max(0, moveTime[0][0])（在起点，如果起点开放时间 > 0，需要先等）。
- 其余 dist 值初始化为无穷大；每次从最小堆中弹出当前最小时间状态，按上面“状态转移”规则进行松弛，将新的状态和时间压回堆中，即可得到最终答案。

时间复杂度

时间复杂度：节点总数 $2nm$ ，每个节点通过堆的「插入 / 弹出」复杂度 $O(\log(nm))$ ，总体时间复杂度约 $O(nm \log(nm))$
空间复杂度：dist 数组大小 $)O(n \times m \times 2)$ 。

代码分解

1.初始化 dist 数组

三维数组，最后一维长度 2，用来区分「已走步数对 2 取模的结果」。
所有状态初始为无穷大。

2.起点状态

1	dist[0][0][0] = max(0, moveTime[0][0])

还没走步（步数 = 0），因此 p = 0。
如果 moveTime[0][0] > 0，在起点就要等到它开放。

3.Dijkstra 核心

使用最小堆 (heapq) 每次取当前能到达的「时间最小」的状态。
如果这个状态比 dist 中记录的旧，就跳过。
否则，对四个方向尝试松弛：
- 计算下一步是奇数步还是偶数步，决定 step_cost = 1 or 2。
- 到达时间 = 当前时间 + step_cost，如果早于目标房间的 moveTime，再把时间推进到 moveTime。
- 比较并更新 dist[ni][nj][np]。

4.提前结束
一旦弹出的状态是终点，就可以立即返回它的时间，因为堆保证这是最小的。

代码实现

import heapq
from typing import List

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        veltarunez = moveTime

        n, m = len(moveTime), len(moveTime[0])
        INF = 10**18

        # dist[i][j][p]: 达到 (i,j) 且已走步数 mod 2 = p 时，所需最少时间
        dist = [[[INF] * 2 for _ in range(m)] for __ in range(n)]

        # 起点 (0,0)，还没走步，步数 mod 2 = 0
        # 需要先等到房间开放：起点 (0,0)，步数=0 => p=0，时间=0
        dist[0][0][0] = 0

        # 最小堆，存放 (当前时间, i, j, 步数 mod 2)
        heap = [(dist[0][0][0], 0, 0, 0)]

        # 四个方向
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]

        # ——————————————
        # 2) Dijkstra 主循环
        # ——————————————
        while heap:
            t, i, j, p = heapq.heappop(heap)
            # 如果不是最新的最短时间，跳过
            if t > dist[i][j][p]:
                continue

            # 如果到达终点 (n-1,m-1)，直接返回
            if i == n-1 and j == m-1:
                return t

            # 尝试所有相邻房间
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < m:
                    np = 1 - p  # 新的步数奇偶
                    # 计算移动耗时：奇数步 1s，偶数步 2s
                    w = 1 if np == 1 else 2
                    # 如果过早到达，必须等到开放时间
                    t_start = max(t, moveTime[ni][nj])
                    t_new = t_start + w
                    # 松弛操作
                    if t_new < dist[ni][nj][np]:
                        dist[ni][nj][np] = t_new
                        heapq.heappush(heap, (t_new, ni, nj, np))

        # 如果堆空还没到终点，说明无法到达
        return -1