Hard
题目描述
给你一个 m x n 的矩阵 grid，由非负整数组成，其中 grid[row][col] 表示可以访问单元格 (row, col) 的 最早时间，也就是说当你访问单元格 (row, col) 时，最少需要等待的时间为 grid[row][col]。
你从矩阵的 左上角 出发，在第 0 秒时，你可以在单元格 (0, 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
解题思路
这道题是一个最短路径问题的变种，核心在于理解时间限制和等待机制。
关键观察：
- 如果当前时间小于目标单元格的时间要求，我们需要等待或者来回移动来"消耗时间"
- 当我们不能直接到达某个单元格时，可以在两个相邻单元格之间来回移动来消耗时间
- 如果起始位置的相邻单元格时间要求都大于1，且我们无法通过来回移动到达它们，则无解
算法思路： 使用 Dijkstra 算法 求最短路径，但需要处理时间等待的逻辑：
- 无解判断：如果
grid[0][1] > 1且grid[1][0] > 1，则无法离开起始位置，返回 -1 - 时间计算：当到达某个单元格时，如果当前时间小于该单元格的时间要求，需要计算等待时间
- 如果时间差为偶数，可以通过来回移动正好在要求时间到达
- 如果时间差为奇数，需要额外等待1秒
- 优先队列：使用最小堆维护
(时间, 行, 列)，每次取出时间最小的状态进行扩展
推荐解法：Dijkstra + 时间等待逻辑处理
代码实现
class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
// 无解情况：无法离开起始位置
if (grid[0][1] > 1 && grid[1][0] > 1) {
return -1;
}
// Dijkstra算法
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;
dist[0][0] = 0;
pq.push({0, 0, 0}); // {时间, 行, 列}
int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
int time = curr[0], row = curr[1], col = curr[2];
if (row == m - 1 && col == n - 1) {
return time;
}
if (time > dist[row][col]) continue;
for (auto& dir : dirs) {
int nr = row + dir[0], nc = col + dir[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
int newTime = time + 1;
// 如果当前时间不够，需要等待或来回移动
if (newTime < grid[nr][nc]) {
int wait = grid[nr][nc] - newTime;
// 如果等待时间是奇数，需要额外等待1秒
newTime = grid[nr][nc] + (wait % 2);
}
if (newTime < dist[nr][nc]) {
dist[nr][nc] = newTime;
pq.push({newTime, nr, nc});
}
}
}
}
return -1;
}
};
class Solution:
def minimumTime(self, grid: List[List[int]]) -> int:
import heapq
m, n = len(grid), len(grid[0])
# 无解情况：无法离开起始位置
if grid[0][1] > 1 and grid[1][0] > 1:
return -1
# Dijkstra算法
dist = [[float('inf')] * n for _ in range(m)]
pq = [(0, 0, 0)] # (时间, 行, 列)
dist[0][0] = 0
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while pq:
time, row, col = heapq.heappop(pq)
if row == m - 1 and col == n - 1:
return time
if time > dist[row][col]:
continue
for dr, dc in dirs:
nr, nc = row + dr, col + dc
if 0 <= nr < m and 0 <= nc < n:
new_time = time + 1
# 如果当前时间不够，需要等待或来回移动
if new_time < grid[nr][nc]:
wait = grid[nr][nc] - new_time
# 如果等待时间是奇数，需要额外等待1秒
new_time = grid[nr][nc] + (wait % 2)
if new_time < dist[nr][nc]:
dist[nr][nc] = new_time
heapq.heappush(pq, (new_time, nr, nc))
return -1
public class Solution {
public int MinimumTime(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
// 无解情况：无法离开起始位置
if (grid[0][1] > 1 && grid[1][0] > 1) {
return -1;
}
// Dijkstra算法
int[,] dist = new int[m, n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dist[i, j] = int.MaxValue;
}
}
var pq = new PriorityQueue<(int time, int row, int col), int>();
dist[0, 0] = 0;
pq.Enqueue((0, 0, 0), 0);
int[,] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (pq.Count > 0) {
var (time, row, col) = pq.Dequeue();
if (row == m - 1 && col == n - 1) {
return time;
}
if (time > dist[row, col]) continue;
for (int i = 0; i < 4; i++) {
int nr = row + dirs[i, 0], nc = col + dirs[i, 1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
int newTime = time + 1;
// 如果当前时间不够，需要等待或来回移动
if (newTime < grid[nr][nc]) {
int wait = grid[nr][nc] - newTime;
// 如果等待时间是奇数，需要额外等待1秒
newTime = grid[nr][nc] + (wait % 2);
}
if (newTime < dist[nr, nc]) {
dist[nr, nc] = newTime;
pq.Enqueue((newTime, nr, nc), newTime);
}
}
}
}
return -1;
}
}
var minimumTime = function(grid) {
const m = grid.length;
const n = grid[0].length;
if (grid[0][1] > 1 && grid[1][0] > 1) {
return -1;
}
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const visited = Array(m).fill().map(() => Array(n).fill(false));
const pq = [[0, 0, 0]]; // [time, row, col]
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]);
const [time, row, col] = pq.shift();
if (row === m - 1 && col === n - 1) {
return time;
}
if (visited[row][col]) {
continue;
}
visited[row][col] = true;
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
let nextTime = time + 1;
if (nextTime < grid[newRow][newCol]) {
const wait = grid[newRow][newCol] - nextTime;
nextTime = grid[newRow][newCol] + (wait % 2);
}
pq.push([nextTime, newRow, newCol]);
}
}
}
return -1;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(mn log(mn)) |
| 空间复杂度 | O(mn) |
说明：
- 时间复杂度：Dijkstra算法中每个节点最多被访问一次，优先队列操作为 O(log(mn))，总共有 mn 个节点
- 空间复杂度：距离数组和优先队列的空间开销都是 O(mn)