在网格图中访问一个格子的最少时间

难度: Hard

给你一个 m x n 的矩阵 grid ，每个元素都为非负整数，其中 grid[row][col] 表示可以访问格子 (row, col) 的最早时间。也就是说当你访问格子 (row, col) 时，最少已经经过的时间为 grid[row][col] 。

你从 最左上角 出发，出发时刻为 0 ，你必须一直移动到上下左右相邻四个格子中的任意一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。

请你返回最早到达右下角格子的时间，如果你无法到达右下角的格子，请你返回 -1 。

示例 1：

输入：grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
输出：7
解释：一条可行的路径为：
- 时刻 t = 0 ，我们在格子 (0,0) 。
- 时刻 t = 1 ，我们移动到格子 (0,1) ，可以移动的原因是 grid[0][1] <= 1 。
- 时刻 t = 2 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 2 。
- 时刻 t = 3 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 3 。
- 时刻 t = 4 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 4 。
- 时刻 t = 5 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 5 。
- 时刻 t = 6 ，我们移动到格子 (1,3) ，可以移动的原因是 grid[1][3] <= 6 。
- 时刻 t = 7 ，我们移动到格子 (2,3) ，可以移动的原因是 grid[2][3] <= 7 。
最终到达时刻为 7 。这是最早可以到达的时间。

示例 2：

输入：grid = [[0,2,4],[3,2,1],[1,0,4]]
输出：-1
解释：没法从左上角按题目规定走到右下角。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 10⁵
0 <= grid[i][j] <= 10⁵
grid[0][0] == 0

Submission

运行时间: 728 ms

内存: 29.1 MB

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        m=len(grid)
        n=len(grid[0])
        if grid[0][1]>1 and grid[1][0]>1:return -1
        dis=[[inf]*n for _ in range(m)]
        dis[0][0]=0
        face=[(-1,0),(1,0),(0,-1),(0,1)]
        h=[(0,0,0)]
        while h:
            dx,i,j=heappop(h)
            if i==m-1 and j==n-1:return dx
            if dx>dis[i][j]:continue
            for x1,y1 in face:
                n_x=i+x1
                n_y=j+y1
                if n_x<0 or n_y<0 or n_x>=m or n_y>=n:continue
                new_d=dx+1
                #if (i,j)==(0,0) and new_d<grid[n_x][n_y]:continue
                if new_d<grid[n_x][n_y]:
                    k=grid[n_x][n_y]-dx
                    if k%2:new_d=grid[n_x][n_y]
                    else:new_d=grid[n_x][n_y]+1
                if new_d<dis[n_x][n_y]:
                    dis[n_x][n_y]=new_d
                    heappush(h,(new_d,n_x,n_y))
        return -1

Explain

这道题目利用的是优先队列（最小堆）的方式来找出最早到达矩阵右下角的路径。算法开始时，将起始点 (0, 0) 的时间为 0 加入堆中。然后，依次从堆中取出当前时间最小的点，更新它的邻居节点。如果移动到邻居节点的时间小于该邻居节点在 grid 中指定的最早可访问时间，那么我们需要等待，直到满足条件。我们不断地从堆中取点和更新点，直到到达矩阵的右下角。如果在某个点的时间超过了我们在此之前访问过该点的时间，就无需再处理它。这是因为我们已经找到了一种更早到达该点的方式。如果我们在堆为空时还没有到达终点，说明无法到达终点，返回 -1。

时间复杂度: O((m*n) * log(m*n))

空间复杂度: O(m*n)

# 这个类包含了计算网格图中从左上角到右下角的最少时间的方法

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        m = len(grid)  # 行数
        n = len(grid[0])  # 列数
        # 检查是否可以从 (0,0) 点开始
        if grid[0][1] > 1 and grid[1][0] > 1: return -1
        dis = [[float('inf')] * n for _ in range(m)]  # 初始化距离矩阵
        dis[0][0] = 0  # 起点的最小时间是0
        face = [(-1,0), (1,0), (0,-1), (0,1)]  # 可以移动的四个方向
        h = [(0,0,0)]  # 初始化堆，包含起始点
        while h:
            dx, i, j = heappop(h)  # 弹出当前最早可达的点
            if i == m-1 and j == n-1: return dx  # 如果到达终点，返回当前时间
            if dx > dis[i][j]: continue  # 如果当前时间不是最优的，跳过
            for x1, y1 in face:
                n_x = i + x1
                n_y = j + y1
                if n_x < 0 or n_y < 0 or n_x >= m or n_y >= n: continue  # 检查边界
                new_d = dx + 1  # 计算新的时间
                # 判断是否需要等待以满足访问条件
                if new_d < grid[n_x][n_y]:
                    k = grid[n_x][n_y] - dx
                    if k % 2: new_d = grid[n_x][n_y]  # 如果需要等待奇数时间，设置等待后的时间
                    else: new_d = grid[n_x][n_y] + 1  # 如果是偶数时间，等待一个单位时间
                if new_d < dis[n_x][n_y]:
                    dis[n_x][n_y] = new_d  # 更新到达该点的最早时间
                    heappush(h, (new_d, n_x, n_y))  # 将更新后的点放入堆中
        return -1  # 如果堆为空仍未到达终点，返回-1

Explore

优先队列（最小堆）能够保证总是从队列中取出当前具有最小计时的节点，这对于本题中寻找最短路径至关重要。使用最小堆可以快速地访问并更新到达每个点的最早可能时间，确保算法的效率。这种结构适合处理问题，因为它可以高效地管理和更新待处理节点的优先级，适用于图中的最短路径搜索，如Dijkstra算法。

在本题的优先队列中，元素按照从网格的起点（左上角）到当前点的时间（距离）进行排序，具有最小时间的点优先处理。选择这种排序方式可以确保每次都处理当前可达的最早的点，这有助于快速找到路径，并在满足条件时立即停止进一步搜索，从而提高效率。

如果堆为空时仍未到达终点，通常表明从起点到终点之间存在不可逾越的障碍或条件限制，使得路径不可到达。例如，如果起始点周围的单元格的时间值过高，导致无法从起点开始。从输入数据的角度预测这种情况，可以检查起始点周围的邻居节点的时间值，如果这些值都设置得过高，或者网格配置使得所有通路都被封锁，那么可能预见到返回 -1 的情况。