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

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

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

思路分析

这是一个典型的 **最短路径问题。

不记录最短时间表，而是让优先队列自动保证我们最先到达终点
当访问一个节点时，我们才标记为已访问，确保最优路径被优先处理

python

import heapq
from typing import List

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        pq = [(0, 0, 0)]  # (time, row, col)
        visited = [[False]*m for _ in range(n)]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while pq:
            time, r, c = heapq.heappop(pq)
            
            if r == n-1 and c == m-1:
                return time
            
            if visited[r][c]:
                continue
                
            visited[r][c] = True
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc]:
                    wait_time = max(time, moveTime[nr][nc])
                    heapq.heappush(pq, (wait_time + 1, nr, nc))
        
        return -1

⏱️ 时间复杂度分析

每个节点最多被访问一次，堆操作为 O(log nm)
总体复杂度：O(nm * log(nm))，适用于题目限制 n,m ≤ 50

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

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