| comments | difficulty | edit_url | rating | source | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2381 |
第 334 场周赛 Q4 |
|
给你一个 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))class Solution {
public int minimumTime(int[][] grid) {
if (grid[0][1] > 1 && grid[1][0] > 1) {
return -1;
}
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (var e : dist) {
Arrays.fill(e, 1 << 30);
}
dist[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[] {0, 0, 0});
int[] dirs = {-1, 0, 1, 0, -1};
while (true) {
var p = pq.poll();
int i = p[1], j = p[2];
if (i == m - 1 && j == n - 1) {
return p[0];
}
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
int nt = p[0] + 1;
if (nt < grid[x][y]) {
nt = grid[x][y] + (grid[x][y] - nt) % 2;
}
if (nt < dist[x][y]) {
dist[x][y] = nt;
pq.offer(new int[] {nt, x, y});
}
}
}
}
}
}class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
if (grid[0][1] > 1 && grid[1][0] > 1) {
return -1;
}
int m = grid.size(), n = grid[0].size();
int dist[m][n];
memset(dist, 0x3f, sizeof dist);
dist[0][0] = 0;
using tii = tuple<int, int, int>;
priority_queue<tii, vector<tii>, greater<tii>> pq;
pq.emplace(0, 0, 0);
int dirs[5] = {-1, 0, 1, 0, -1};
while (1) {
auto [t, i, j] = pq.top();
pq.pop();
if (i == m - 1 && j == n - 1) {
return t;
}
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
int 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;
pq.emplace(nt, x, y);
}
}
}
}
}
};func minimumTime(grid [][]int) int {
if grid[0][1] > 1 && grid[1][0] > 1 {
return -1
}
m, n := len(grid), len(grid[0])
dist := make([][]int, m)
for i := range dist {
dist[i] = make([]int, n)
for j := range dist[i] {
dist[i][j] = 1 << 30
}
}
dist[0][0] = 0
pq := hp{}
heap.Push(&pq, tuple{0, 0, 0})
dirs := [5]int{-1, 0, 1, 0, -1}
for {
p := heap.Pop(&pq).(tuple)
i, j := p.i, p.j
if i == m-1 && j == n-1 {
return p.t
}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n {
nt := p.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
heap.Push(&pq, tuple{nt, x, y})
}
}
}
}
}
type tuple struct{ t, i, j int }
type hp []tuple
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].t < h[j].t }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }