跳转至

3342. 到达最后一个房间的最少时间 II

来源第 422 场周赛 Q3难度中等分数1861

题目描述

有一个地窖,地窖中有 n x m 个房间,它们呈网格状排布。

给你一个大小为 n x m 的二维数组 moveTime ,其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发,每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为:第一次花费 1 秒,第二次花费 2 秒,第三次花费 1 秒,第四次花费 2 秒……如此 往复 。

请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。

如果两个房间有一条公共边(可以是水平的也可以是竖直的),那么我们称这两个房间是 相邻 的。

 

示例 1:

输入:moveTime = [[0,4],[4,4]]

输出:7

解释:

需要花费的最少时间为 7 秒。

  • 在时刻 t == 4 ,从房间 (0, 0) 移动到房间 (1, 0) ,花费 1 秒。
  • 在时刻 t == 5 ,从房间 (1, 0) 移动到房间 (1, 1) ,花费 2 秒。

示例 2:

输入:moveTime = [[0,0,0,0],[0,0,0,0]]

输出:6

解释:

需要花费的最少时间为 6 秒。

  • 在时刻 t == 0 ,从房间 (0, 0) 移动到房间 (1, 0) ,花费 1 秒。
  • 在时刻 t == 1 ,从房间 (1, 0) 移动到房间 (1, 1) ,花费 2 秒。
  • 在时刻 t == 3 ,从房间 (1, 1) 移动到房间 (1, 2) ,花费 1 秒。
  • 在时刻 t == 4 ,从房间 (1, 2) 移动到房间 (1, 3) ,花费 2 秒。

示例 3:

输入:moveTime = [[0,1],[1,2]]

输出:4

 

提示:

  • 2 <= n == moveTime.length <= 750
  • 2 <= m == moveTime[i].length <= 750
  • 0 <= moveTime[i][j] <= 109

解法

方法一:Dijkstra 算法

思考

与 I 相比,奇偶步交替耗时 \(1\) 与 \(2\),且网格更大。最短路模型不变,只是边权变成 \(\max(\textit{moveTime}[x][y],d)+(i+j)\bmod 2+1\)。

\((i+j)\bmod 2\) 恰为到达 \((i,j)\) 后下一步的奇偶:从 \((0,0)\) 出发,下一步耗时 \(1\),再下一步耗时 \(2\),与坐标奇偶一致。

仍用 Dijkstra 按时间松弛;终点首次出堆即为答案。

我们定义一个二维数组 \(\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]) + (i + 2) \bmod 2 + 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]) + (i + j) % 2 + 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]) + (i + j) % 2 + 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]) + (i + j) % 2 + 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]) + (i+j)%2 + 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) + ((i + j) % 2) + 1;
                if (t < dist[x][y]) {
                    dist[x][y] = t;
                    pq.enqueue([t, x, y]);
                }
            }
        }
    }
    return -1;
}

评论