There is a dungeon with n x m rooms arranged as a grid.
You are given a 2D array moveTime of size n x m, where moveTime[i][j] represents the minimum time in seconds when you can start moving to that room. You start from the room (0, 0) at time t = 0 and can move to an adjacent room. Moving between adjacent rooms takes exactly one second.
Return the minimum time to reach the room (n - 1, m - 1).
Two rooms are adjacent if they share a common wall, either horizontally or vertically.
Example 1:
Input: moveTime = [[0,4],[4,4]]
Output: 6
Explanation:
The minimum time required is 6 seconds.
t == 4, move from room (0, 0) to room (1, 0) in one second.t == 5, move from room (1, 0) to room (1, 1) in one second.Example 2:
Input: moveTime = [[0,0,0],[0,0,0]]
Output: 3
Explanation:
The minimum time required is 3 seconds.
t == 0, move from room (0, 0) to room (1, 0) in one second.t == 1, move from room (1, 0) to room (1, 1) in one second.t == 2, move from room (1, 1) to room (1, 2) in one second.Example 3:
Input: moveTime = [[0,1],[1,2]]
Output: 3
Constraints:
2 <= n == moveTime.length <= 502 <= m == moveTime[i].length <= 500 <= moveTime[i][j] <= 109class Solution {
int[][] dirs = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };
private boolean isValid(int x, int y, int m, int n) {
return x >= 0 && y >= 0 && x < m && y < n;
}
public int minTimeToReach(int[][] moveTime) {
int m = moveTime.length, n = moveTime[0].length;
int[][] minReachTime = new int[m][n];
boolean[][] vis = new boolean[m][n];
for (int[] r : minReachTime)
Arrays.fill(r, Integer.MAX_VALUE);
Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
pq.offer(new int[] { 0, 0, 0 });
while (!pq.isEmpty()) {
int[] top = pq.poll();
// System.out.println(Arrays.toString(top));
int x = top[0], y = top[1], reachedAt = top[2];
if (vis[x][y])
continue;
vis[x][y] = true;
if (x == m - 1 && y == n - 1)
return reachedAt;
if (minReachTime[x][y] > reachedAt) {
minReachTime[x][y] = reachedAt;
bfs(x, y, m, n, reachedAt, moveTime, pq);
}
}
return minReachTime[m - 1][n - 1];
}
private void bfs(int x, int y, int m, int n, int timeElapsed,
int[][] moveTime, Queue<int[]> pq) {
for (int[] d : dirs) {
int X = x + d[0], Y = y + d[1];
if (isValid(X, Y, m, n))
pq.offer(new int[] { X, Y, Math.max(timeElapsed + 1, moveTime[X][Y] + 1) });
}
}
}