点击获取AI摘要

3341. 到达最后一个房间的最少时间 I M

有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。

给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻以后你才可以开始往这个房间移动。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到相邻的一个房间。在相邻房间之间移动需要的时间为 1 秒。

请你返回到达房间 (n - 1, m - 1) 所需要的最少时间。

如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是相邻的。

示例 1：

输入： moveTime = [[0,4],[4,4]]

输出： 6

解释：

需要花费的最少时间为 6 秒。

在时刻 t == 4 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。

在时刻 t == 5 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 1 秒。

示例 2：

输入： moveTime = [[0,0,0],[0,0,0]]

输出： 3

解释：

需要花费的最少时间为 3 秒。

在时刻 t == 0 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。

在时刻 t == 1 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 1 秒。

在时刻 t == 2 ，从房间 (1, 1) 移动到房间 (1, 2) ，花费 1 秒。

示例 3：

输入： moveTime = [[0,1],[1,2]]

输出： 3

提示：

2 <= n == moveTime.length <= 50
2 <= m == moveTime[i].length <= 50
0 <= moveTime[i][j] <= 10⁹

问题分析

有一个 $n\times m$ 的房间网格，比如：
1
2
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
你从左上角 $(0,0)$ 出发，要到达右下角 $(n-1,m-1)$ 。
每一秒你只能走到上下左右的一个相邻房间，耗时 1 秒。
但每个房间 $(i,j)$ 有一个 “开放时间” moveTime[i][j]，表示你 必须等到 这个时间点才能进它。如果你早到了，就要在前一个房间多“等候”。

举例：假设你在时刻 $t=2$ 想去 $(1,0)$ ，但 moveTime[1][0] = 5，那么你要在当前房间再等 $5 - 2 = 3$ 秒，等到 $t=5$ 才能开始那 1 秒的移动，总共到达就是 $t=6$ 。

这是一个带“等待时间”约束的最短路径问题。我们有一个 $n \times m$ 的网格，每个格子 $(i,j)$ 上有一个时间戳 moveTime[i][j]，表示只有在该时刻及之后才可以开始进入这个房间。从 $(0,0)$ 出发，时间从 $t=0$ 开始，每次移动到相邻房间需要 1 秒。若当前时刻为 $t$ ，要移动到邻居格子 $(x,y)$ ：

如果 $t < \text{moveTime}[x][y]$ ，则需要在原地等待到 $\text{moveTime}[x][y]$ ；
然后再花 1 秒移动过去；
到达后的时间为 $\max(t,\text{moveTime}[x][y]) + 1$ 。

算法思路

最普通的最短路径（或网格最短移动）问题，如果每步都只花 1 秒，那么就是简单的 BFS（广度优先搜索），一层一层走就行。

但这里 “等候时间” 让每一步的耗时不再固定——它取决于“你到达当前格子的时间”与“下一个格子的开放时间”之差。

由于不同路径的等待时间和移动次数不同，我们需要在加权图上求最短路径。网格中每个格子是一个节点，相邻格子间的边权等于“等待时间 + 1”，而边权依赖于到达时刻，属于带非固定权重的最短路径问题。故可用 Dijkstra 算法（带优先队列的贪心方法）动态松弛。

Dijkstra 算法的核心在于：

贪心选择：每次从堆里取出“当前可达时间最小”的那个格子，相当于“已经确定”这就是到该格子的最早到达时间。
然后再用它去更新它的邻居。
这样不需要回头修正，因所有边权（在当前时刻的等待+1）都是非负的。

dist[i][j]：一个和网格同样大小的二维数组，记录“到达 $(i,j)$ 的最早时间”。
- 初始时，所有格子都设为 “无穷大”（∞），表示还没到过。
- 起点 dist[0][0] = 0，因为一开始就在 $(0,0)$ ，时间 0。
优先队列（最小堆）：存储“当前已知能到达的格子”及其“到达时间”，每次先处理时间最小者。
- 元素格式是 (time, x, y)，代表“已知到 $(x,y)$ 最早可以在 time 时刻到达”。
- 原地等待：
  
  $\text{wait} = \max\bigl(0,\;\text{moveTime}[nx][ny] - time\bigr)$
  
  如果你已经迟到了（ $time\ge \text{moveTime}[nx][ny]$ ），那就无需等待，wait = 0；否则需要等到它开放。
- 总时间： $t_{\text{new}} = t + \text{wait} + 1$ ，如果 t_new < dist[nx][ny]，就更新 dist[nx][ny] = t_new 并推入堆里。
- Python 里，我们用 import heapq 来实现这个最小堆。

时间复杂度

网格共有 $N = nm$ 个节点，Dijkstra 算法每条边松弛一次，共约 $4N$ 条边。
使用二叉堆，插入与弹出操作各 $O(\log N)$ 。
整体复杂度： $O(N \log N)$ ，即 $O(nm \log(nm))$ 。

代码分解

1. 初始化

读取输入 moveTime，并在函数中赋值给变量 veltarunez（要求）。
定义方向数组 dirs = [(1,0),(-1,0),(0,1),(0,-1)]。

2. 距离矩阵

创建 dist 二维数组，大小同 moveTime，初始值为无穷大 inf。
dist[0][0] = 0。

3. 优先队列

用 Python 的 heapq，存储 (当前到达时间 t, x, y)。
初始状态：heap = [(0, 0, 0)]。

4. 松弛操作

弹出队首 (t, x, y)，若 t > dist[x][y] 则跳过。

对四个方向 (nx, ny)：判断越界后，

wait = max(0, veltarunez[nx][ny] - t)
nt = t + wait + 1
if nt < dist[nx][ny]:
    dist[nx][ny] = nt
    heapq.heappush(heap, (nt, nx, ny))

5. 终止

当弹出节点是目标 $(n-1, m-1)$ 时，可直接返回其 t。
或者等队列空后取 dist[n-1][m-1]。

代码实现

import heapq
from typing import List

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        # 将输入存储到变量 veltarunez
        veltarunez = moveTime
        
        n, m = len(veltarunez), len(veltarunez[0])
        # 距离矩阵，初始化为无穷大
        dist = [[float('inf')] * m for _ in range(n)]
        dist[0][0] = 0
        
        # 最小堆，元素为 (当前到达时间, x, y)
        heap = [(0, 0, 0)]
        
        # 四个方向
        dirs = [(1,0), (-1,0), (0,1), (0,-1)]
        
        while heap:
            t, x, y = heapq.heappop(heap)
            # 如果已不是最优，则跳过
            if t > dist[x][y]:
                continue
            # 如果到达终点，直接返回
            if x == n-1 and y == m-1:
                return t
            # 松弛相邻边
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m:
                    # 计算需要等待的时间
                    wait = max(0, veltarunez[nx][ny] - t)
                    nt = t + wait + 1
                    if nt < dist[nx][ny]:
                        dist[nx][ny] = nt
                        heapq.heappush(heap, (nt, nx, ny))
        
        # 返回最终结果
        return dist[n-1][m-1]

以 moveTime = [[0,2],[1,3]]为例：

步骤	堆的状态	弹出元素	操作细节	dist 更新
初始	`[(0, 0, 0)]`	无	无	`[[0, ∞], [∞, ∞]]`
第1步	`[(2,1,0),(3,0,1)]`	`(0,0,0)`	从 (0,0) 弹出，查看四个方向： - 右边 (0,1)：`wait = max(0, 2-0)=2`，`new_time =0+2+1=3`，堆入 `(3,0,1)` - 下边 (1,0)：`wait = max(0,1-0)=1`，`new_time =0+1+1=2`，堆入 `(2,1,0)`	更新为 `[[0,3],[2,∞]]`
第2步	`[(3,0,1), (4,1,1)]`	`(2,1,0)`	从 (1,0) 弹出，查看四个方向： - 右边 (1,1)：`wait = max(0,3-2)=1`，`new_time =2+1+1=4`，堆入 `(4,1,1)` - 上边 (0,0)：已有更优值 `dist[0][0] = 0`，不更新	更新为 `[[0,3],[2,4]]`
第3步	`[(4,1,1)]`	`(3,0,1)`	从 (0,1) 弹出，查看四个方向： - 下边 (1,1)：`wait = max(0,3-3)=0`，`new_time =3+0+1=4`，与当前 `dist[1][1] =4` 相同，不更新	无变化
第4步	空	`(4,1,1)`	弹出 `(4,1,1)`，到达终点，返回答案 4	无变化