Find Minimum Time to Reach Last Room I
Problem
A dungeon is an n × m grid of rooms. moveTime[i][j] is the earliest second at which room (i, j) opens and may be entered. You start at (0, 0) at time t = 0; each move to an orthogonally adjacent room takes exactly one second. To step into a neighbor you must first wait until it opens, so leaving at time t you arrive at max(t, moveTime[neighbor]) + 1. Return the minimum time to reach (n − 1, m − 1).
moveTime = [[0,4],[4,4]]6import heapq
def minTimeToReach(moveTime):
n, m = len(moveTime), len(moveTime[0])
INF = float("inf")
dist = [[INF] * m for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)] # (time, row, col)
while pq:
t, r, c = heapq.heappop(pq)
if t > dist[r][c]: # stale entry, skip
continue
if r == n - 1 and c == m - 1: # reached the last room
return t
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m:
nt = max(t, moveTime[nr][nc]) + 1 # wait, then move
if nt < dist[nr][nc]:
dist[nr][nc] = nt
heapq.heappush(pq, (nt, nr, nc))
return dist[n - 1][m - 1]function minTimeToReach(moveTime) {
const n = moveTime.length, m = moveTime[0].length;
const dist = Array.from({ length: n }, () => Array(m).fill(Infinity));
dist[0][0] = 0;
const pq = [[0, 0, 0]]; // [time, row, col] min-heap
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]); // smallest time first
const [t, r, c] = pq.shift();
if (t > dist[r][c]) continue; // stale entry, skip
if (r === n - 1 && c === m - 1) return t;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
const nt = Math.max(t, moveTime[nr][nc]) + 1; // wait, then move
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push([nt, nr, nc]);
}
}
}
return dist[n - 1][m - 1];
}int minTimeToReach(int[][] moveTime) {
int n = moveTime.length, m = moveTime[0].length;
int[][] dist = new int[n][m];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = 0;
// min-heap on time: {time, row, col}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, 0, 0});
int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int t = cur[0], r = cur[1], c = cur[2];
if (t > dist[r][c]) continue; // stale entry, skip
if (r == n - 1 && c == m - 1) return t;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
int nt = Math.max(t, moveTime[nr][nc]) + 1; // wait, then move
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.offer(new int[]{nt, nr, nc});
}
}
}
return dist[n - 1][m - 1];
}int minTimeToReach(vector<vector<int>>& moveTime) {
int n = moveTime.size(), m = moveTime[0].size();
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
dist[0][0] = 0;
// min-heap of {time, row, col}
priority_queue<array<int,3>, vector<array<int,3>>, greater<>> pq;
pq.push({0, 0, 0});
int dirs[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
while (!pq.empty()) {
auto [t, r, c] = pq.top(); pq.pop();
if (t > dist[r][c]) continue; // stale entry, skip
if (r == n - 1 && c == m - 1) return t;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
int nt = max(t, moveTime[nr][nc]) + 1; // wait, then move
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push({nt, nr, nc});
}
}
}
return dist[n - 1][m - 1];
}Explanation
Think of each room as a graph node and each shared wall as an edge. We want the earliest possible arrival time at the bottom-right room, so this is a shortest-path problem where the "distance" is time.
The twist is the edge cost. If you are standing in a room at time t and want to step into a neighbor, that neighbor might not have opened yet. You must wait until moveTime[neighbor], then spend one second moving. So the arrival time at the neighbor is max(t, moveTime[neighbor]) + 1. Because this cost is always non-negative, Dijkstra's algorithm applies.
We keep a dist grid (best known arrival time per room, initialized to infinity except the start at 0) and a min-heap keyed on time. Each step we pop the room with the smallest arrival time. If that time is worse than the recorded dist it is a stale leftover and we skip it. Otherwise the room is now settled with its true minimum, and we relax its four neighbors, pushing any improvement back onto the heap.
The first time we pop the target room (n − 1, m − 1), its time is final, so we return it immediately. This early exit is safe precisely because the heap always hands back the smallest unsettled time.
Example: for [[0,4],[4,4]] the start opens at 0. Both neighbors open at 4, so we wait and arrive at either at time 5, then step into (1,1) arriving at time 6 — the answer.