目标
有一个地窖，地窖中有 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 <= 50
- 2 <= m == moveTime[i].length <= 50
- 0 <=
moveTime[i][j]<= 10^9
思路
求从 (0, 0) 到达 (n - 1, m - 1) 所需的最少时间，从相邻格子移动需要耗时 1 秒，并且 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动。
这是一个最短路径问题，使用 Dijkstra 算法。
代码
/**
* @date 2025-05-07 8:50
*/
public class MinTimeToReach3341 {
public int minTimeToReach(int[][] moveTime) {
int n = moveTime.length;
int m = moveTime[0].length;
int[][] dist = dijkstra(moveTime);
return dist[n - 1][m - 1];
}
private int[][] dijkstra(int[][] g) {
int n = g.length;
int m = g[0].length;
int[][] dist = new int[n][m];
int[][] directions = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
for (int[] row : dist) {
Arrays.fill(row, Integer.MAX_VALUE);
}
dist[0][0] = 0;
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[2] - b[2]);
q.offer(new int[]{0, 0, 0});
while (!q.isEmpty()) {
int[] cur = q.poll();
int i = cur[0], j = cur[1], waitTime = cur[2];
if (waitTime > dist[i][j]) {
continue;
}
for (int[] direction : directions) {
int x = i + direction[0];
int y = j + direction[1];
if (x < n && x >= 0 && y >= 0 && y < m && dist[x][y] > Math.max(dist[i][j], g[x][y]) + 1) {
dist[x][y] = Math.max(dist[i][j], g[x][y]) + 1;
q.offer(new int[]{x, y, dist[x][y]});
}
}
}
return dist;
}
}
性能
