LeetCode 题解工作台
在网格图中访问一个格子的最少时间
给你一个 m x n 的矩阵 grid ，每个元素都为 非负 整数，其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时，最少已经经过的时间为 grid[row][col] 。 你从 最左上角 出发，出发时刻为 0…
6
题型
6
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
我们观察发现，如果在格子 $(0, 0)$ 处无法移动，即 $grid[0][1] \gt 1$ 且 $grid[1][0] \gt 1$，那么我们在格子 $(0, 0)$ 无法再移动，此时返回 即可。而对于其他情况，我们都可以移动。 接下来，我们定义 表示 $(i, j)$ 处的最早到达时间，初始时 $dist[0][0] = 0$，而其他位置的 均初始化为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个 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.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 1050 <= grid[i][j] <= 105grid[0][0] == 0
解题思路
方法一：最短路 + 优先队列（小根堆）
我们观察发现，如果在格子 处无法移动，即 且 ，那么我们在格子 无法再移动，此时返回 即可。而对于其他情况，我们都可以移动。
接下来，我们定义 表示 处的最早到达时间，初始时 ，而其他位置的 均初始化为 。
我们使用优先队列（小根堆）来维护当前可以移动的格子，优先队列中的元素为 ，即 表示 处的最早到达时间。
我们每次从优先队列中取出当前最早到达的格子 ，如果 为 ，那么我们直接返回 即可，否则，我们遍历 的上下左右四个相邻格子 ，如果 ，那么我们移动到 的时间 ，此时我们可以通过反复移动将时间拉长至不小于 ，这取决于 和 距离的奇偶性。否则，我们移动到 的时间 。如果 ，那么我们更新 ，并将 加入优先队列中。
时间复杂度 ，空间复杂度 。其中 和 分别为网格的行数和列数。
class Solution:
def minimumTime(self, grid: List[List[int]]) -> int:
if grid[0][1] > 1 and grid[1][0] > 1:
return -1
m, n = len(grid), len(grid[0])
dist = [[inf] * n for _ in range(m)]
dist[0][0] = 0
q = [(0, 0, 0)]
dirs = (-1, 0, 1, 0, -1)
while 1:
t, i, j = heappop(q)
if i == m - 1 and j == n - 1:
return t
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
nt = t + 1
if nt < grid[x][y]:
nt = grid[x][y] + (grid[x][y] - nt) % 2
if nt < dist[x][y]:
dist[x][y] = nt
heappush(q, (nt, x, y))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m \cdot n \log(m \cdot n)) |
| 空间 | O(m \cdot n) |
面试官常问的追问
外企场景- question_mark
Focus on BFS and shortest path logic to optimize cell visit times.
- question_mark
Consider how cell constraints may block standard BFS paths and require a priority-based expansion.
- question_mark
Expect questions about handling edge cases where the target is unreachable.
常见陷阱
外企场景- error
Not accounting for the minimum required time per cell can lead to invalid paths.
- error
Using standard BFS without prioritizing earliest arrival time may miss optimal solutions.
- error
Failing to track visited times correctly can cause unnecessary reprocessing and wrong results.
进阶变体
外企场景- arrow_right_alt
Modify the grid so certain cells have negative delays to test early arrival handling.
- arrow_right_alt
Use a hexagonal grid with six neighbors instead of four to adjust BFS logic.
- arrow_right_alt
Change the cost of moving between cells to non-uniform values to test weighted shortest paths.