class Solution {
public:
int minTimeToReach(vector<vector<int>>& moveTime) {
}
};
3342. 到达最后一个房间的最少时间 II
有一个地窖，地窖中有 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 <= 7502 <= m == moveTime[i].length <= 7500 <= moveTime[i][j] <= 109原站题解
java 解法, 执行用时: 199 ms, 内存消耗: 106.1 MB, 提交时间: 2024-11-08 22:14:32
class Solution {
private final static int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int minTimeToReach(int[][] moveTime) {
int n = moveTime.length, m = moveTime[0].length;
int[][] dis = new int[n][m];
for (int[] row : dis) {
Arrays.fill(row, Integer.MAX_VALUE);
}
dis[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.add(new int[]{0, 0, 0});
for (;;) {
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 > dis[i][j]) {
continue;
}
for (int[] q : DIRS) {
int x = i + q[0], y = j + q[1];
if (0 <= x && x < n && 0 <= y && y < m) {
int newDis = Math.max(d, moveTime[x][y]) + (i + j) % 2 + 1;
if (newDis < dis[x][y]) {
dis[x][y] = newDis;
pq.add(new int[]{newDis, x, y});
}
}
}
}
}
}
golang 解法, 执行用时: 218 ms, 内存消耗: 33.6 MB, 提交时间: 2024-11-08 22:13:50
var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func minTimeToReach(moveTime [][]int) (ans int) {
n, m := len(moveTime), len(moveTime[0])
dis := make([][]int, n)
for i := range dis {
dis[i] = make([]int, m)
for j := range dis[i] {
dis[i][j] = math.MaxInt
}
}
dis[0][0] = 0
h := hp{{}}
for {
top := heap.Pop(&h).(tuple)
i, j := top.x, top.y
if i == n-1 && j == m-1 {
return top.dis
}
if top.dis > dis[i][j] {
continue
}
for _, d := range dirs {
x, y := i+d.x, j+d.y
if 0 <= x && x < n && 0 <= y && y < m {
newD := max(top.dis, moveTime[x][y]) + (i+j)%2 + 1
if newD < dis[x][y] {
dis[x][y] = newD
heap.Push(&h, tuple{newD, 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 }
python3 解法, 执行用时: 1641 ms, 内存消耗: 85 MB, 提交时间: 2024-11-08 22:10:31
class Solution:
def minTimeToReach(self, moveTime: List[List[int]]) -> int:
n, m = len(moveTime), len(moveTime[0])
dis = [[inf] * m for _ in range(n)]
dis[0][0] = 0
h = [(0, 0, 0)]
while True:
d, i, j = heappop(h)
if i == n - 1 and j == m - 1:
return d
if d > dis[i][j]:
continue
for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1): # 枚举周围四个格子
if 0 <= x < n and 0 <= y < m:
new_dis = max(d, moveTime[x][y]) + (i + j) % 2 + 1
if new_dis < dis[x][y]:
dis[x][y] = new_dis
heappush(h, (new_dis, x, y))