来源第 422 场周赛 Q2难度中等分数1721
题目描述
有一个地窖，地窖中有 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 <= 502 <= m == moveTime[i].length <= 500 <= moveTime[i][j] <= 109
解法
方法一：Dijkstra 算法
思考
进入格子 \((x,y)\) 不得早于 \(\textit{moveTime}[x][y]\)，且每步耗时 \(1\)。边权非负但依赖到达时间，BFS 不再正确。
\(n,m \le 50\)，以时间为关键字的 Dijkstra 足够。松弛式为 \(t=\max(\textit{moveTime}[x][y],\textit{dist}[i][j])+1\)。
优先队列弹出终点时即为最短时间。
我们定义一个二维数组 \(\textit{dist}\)，其中 \(\textit{dist}[i][j]\) 表示从起点到达房间 \((i, j)\) 所需的最少时间。初始时，我们将 \(\textit{dist}\) 数组中的所有元素设为无穷大，然后将起点 \((0, 0)\) 的 \(\textit{dist}\) 值设为 \(0\)。
我们使用优先队列 \(pq\) 存储每一个状态，其中每个状态由三个值 \((d, i, j)\) 组成，表示从起点到达房间 \((i, j)\) 所需的时间为 \(d\)。初始时，我们将起点 \((0, 0, 0)\) 加入到 \(pq\) 中。
在每一次迭代中，我们取出 \(pq\) 中的队首元素 \((d, i, j)\)，如果 \((i, j)\) 是终点，那么我们返回 \(d\)。如果 \(d\) 大于 \(\textit{dist}[i][j]\)，那么我们跳过这个状态。否则，我们枚举 \((i, j)\) 的四个相邻位置 \((x, y)\)，如果 \((x, y)\) 在地图内，那么我们计算从 \((i, j)\) 到 \((x, y)\) 的最终时间 \(t = \max(\textit{moveTime}[x][y], \textit{dist}[i][j]) + 1\)，如果 \(t\) 小于 \(\textit{dist}[x][y]\)，那么我们更新 \(\textit{dist}[x][y]\) 的值，并将 \((t, x, y)\) 加入到 \(pq\) 中。
时间复杂度 \(O(nm \log (nm))\)，空间复杂度 \(O(nm)\)。其中 \(n\) 和 \(m\) 分别是地图的行数和列数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution:
def minTimeToReach(self, moveTime: list[list[int]]) -> int:
n, m = len(moveTime), len(moveTime[0])
dist = [[inf] * m for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)]
dirs = (-1, 0, 1, 0, -1)
while 1:
d, i, j = heappop(pq)
if i == n - 1 and j == m - 1:
return d
if d > dist[i][j]:
continue
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < m:
t = max(moveTime[x][y], dist[i][j]) + 1
if dist[x][y] > t:
dist[x][y] = t
heappush(pq, (t, x, y))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | class Solution {
public int minTimeToReach(int[][] moveTime) {
int n = moveTime.length;
int m = moveTime[0].length;
int[][] dist = new int[n][m];
for (var row : dist) {
Arrays.fill(row, Integer.MAX_VALUE);
}
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) {
int[] p = pq.poll();
int d = p[0], i = p[1], j = p[2];
if (i == n - 1 && j == m - 1) {
return d;
}
if (d > dist[i][j]) {
continue;
}
for (int k = 0; k < 4; k++) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < m) {
int t = Math.max(moveTime[x][y], dist[i][j]) + 1;
if (dist[x][y] > t) {
dist[x][y] = t;
pq.offer(new int[] {t, x, y});
}
}
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | class Solution {
public:
int minTimeToReach(vector<vector<int>>& moveTime) {
int n = moveTime.size();
int m = moveTime[0].size();
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
dist[0][0] = 0;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
pq.push({0, 0, 0});
int dirs[5] = {-1, 0, 1, 0, -1};
while (1) {
auto [d, i, j] = pq.top();
pq.pop();
if (i == n - 1 && j == m - 1) {
return d;
}
if (d > dist[i][j]) {
continue;
}
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < m) {
int t = max(moveTime[x][y], dist[i][j]) + 1;
if (dist[x][y] > t) {
dist[x][y] = t;
pq.push({t, x, y});
}
}
}
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | func minTimeToReach(moveTime [][]int) int {
n, m := len(moveTime), len(moveTime[0])
dist := make([][]int, n)
for i := range dist {
dist[i] = make([]int, m)
for j := range dist[i] {
dist[i][j] = math.MaxInt32
}
}
dist[0][0] = 0
pq := &hp{}
heap.Init(pq)
heap.Push(pq, tuple{0, 0, 0})
dirs := []int{-1, 0, 1, 0, -1}
for {
p := heap.Pop(pq).(tuple)
d, i, j := p.dis, p.x, p.y
if i == n-1 && j == m-1 {
return d
}
if d > dist[i][j] {
continue
}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < m {
t := max(moveTime[x][y], dist[i][j]) + 1
if dist[x][y] > t {
dist[x][y] = t
heap.Push(pq, tuple{t, x, y})
}
}
}
}
}
type tuple struct{ dis, x, y int }
type hp []tuple
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
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() (v any) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | function minTimeToReach(moveTime: number[][]): number {
const n = moveTime.length;
const m = moveTime[0].length;
const dist = Array.from({ length: n }, () => Array(m).fill(Infinity));
dist[0][0] = 0;
type Node = [number, number, number];
const pq = new PriorityQueue<Node>((a, b) => a[0] - b[0]);
pq.enqueue([0, 0, 0]);
const dirs = [-1, 0, 1, 0, -1];
while (!pq.isEmpty()) {
const [d, i, j] = pq.dequeue();
if (d > dist[i][j]) continue;
if (i === n - 1 && j === m - 1) return d;
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < m) {
const t = Math.max(moveTime[x][y], d) + 1;
if (t < dist[x][y]) {
dist[x][y] = t;
pq.enqueue([t, x, y]);
}
}
}
}
return -1;
}
|