Find Minimum Time to Reach Last Room II
Problem
A dungeon is an n × m grid of rooms. moveTime[i][j] is the earliest time (in seconds) you may start moving into room (i, j). You begin in room (0, 0) at time t = 0 and may step to an adjacent room. Moves alternate in cost: the first move takes 1 second, the next 2 seconds, then 1, then 2, and so on. Return the minimum time to reach room (n − 1, m − 1).
moveTime = [[0,4],[4,4]]7def minTimeToReach(moveTime):
import heapq
n, m = len(moveTime), len(moveTime[0])
INF = float("inf")
dist = [[INF] * m for _ in range(n)] # best arrival time per room
dist[0][0] = 0
pq = [(0, 0, 0)] # (time, row, col)
while pq:
t, r, c = heapq.heappop(pq)
if r == n - 1 and c == m - 1: # popped the goal -> answer
return t
if t > dist[r][c]: # stale entry, skip
continue
cost = 1 if (r + c) % 2 == 0 else 2 # move cost alternates 1,2,1,2
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]) + cost
if nt < dist[nr][nc]: # found a faster way in
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 INF = Infinity;
const dist = Array.from({ length: n }, () => Array(m).fill(INF));
dist[0][0] = 0;
// min-heap of [time, row, col]; small array works for the demo
const pq = [[0, 0, 0]];
const pop = () => { let bi = 0;
for (let i = 1; i < pq.length; i++) if (pq[i][0] < pq[bi][0]) bi = i;
return pq.splice(bi, 1)[0]; };
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (pq.length) {
const [t, r, c] = pop();
if (r === n - 1 && c === m - 1) return t; // goal reached
if (t > dist[r][c]) continue; // stale entry
const cost = (r + c) % 2 === 0 ? 1 : 2; // 1,2,1,2 alternating
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
const nt = Math.max(t, moveTime[nr][nc]) + cost;
if (nt < dist[nr][nc]) { // relax neighbour
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;
long[][] dist = new long[n][m];
for (long[] row : dist) Arrays.fill(row, Long.MAX_VALUE);
dist[0][0] = 0;
// heap entries: {time, row, col}, ordered by time
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.offer(new long[]{0, 0, 0});
int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
while (!pq.isEmpty()) {
long[] cur = pq.poll();
long t = cur[0]; int r = (int) cur[1], c = (int) cur[2];
if (r == n - 1 && c == m - 1) return (int) t; // goal popped
if (t > dist[r][c]) continue; // stale entry
long cost = (r + c) % 2 == 0 ? 1 : 2; // alternating 1,2
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
long nt = Math.max(t, moveTime[nr][nc]) + cost;
if (nt < dist[nr][nc]) { // relax neighbour
dist[nr][nc] = nt;
pq.offer(new long[]{nt, nr, nc});
}
}
}
}
return (int) dist[n - 1][m - 1];
}int minTimeToReach(vector<vector<int>>& moveTime) {
int n = moveTime.size(), m = moveTime[0].size();
vector<vector<long long>> dist(n, vector<long long>(m, LLONG_MAX));
dist[0][0] = 0;
// min-heap of {time, row, col}
using T = array<long long, 3>;
priority_queue<T, vector<T>, greater<T>> 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 (r == n - 1 && c == m - 1) return (int) t; // goal popped
if (t > dist[r][c]) continue; // stale entry
long long cost = (r + c) % 2 == 0 ? 1 : 2; // alternating 1,2
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
long long nt = max(t, (long long) moveTime[nr][nc]) + cost;
if (nt < dist[nr][nc]) { // relax neighbour
dist[nr][nc] = nt;
pq.push({nt, nr, nc});
}
}
}
}
return (int) dist[n - 1][m - 1];
}Explanation
This is a shortest-path problem where the “weight” of an edge is the time spent, so we reach for Dijkstra's algorithm with a min-heap keyed on arrival time.
The twist is two-fold. First, you cannot enter room (i, j) before moveTime[i][j]; if you arrive early you must wait, so the start of a move is max(t, moveTime[nr][nc]). Second, the cost of a move alternates 1, 2, 1, 2, … depending on how many moves you have already made.
How do we know the parity of the move count at a cell without storing it? On a grid every path from (0, 0) to (r, c) has a length whose parity equals (r + c) % 2, because each step changes r + c by exactly one. So the next move leaving (r, c) costs 1 when (r + c) is even and 2 when it is odd — no extra state needed.
We pop the cell with the smallest arrival time, and the moment we pop the goal (n−1, m−1) we know its time is final and return it. For every in-bounds neighbour we compute nt = max(t, moveTime[nr][nc]) + cost and relax it into the heap when it improves the best known time.
Example: moveTime = [[0,4],[4,4]]. From (0,0) the move cost is 1; entering (1,0) we must wait until t=4, arriving at t=5. From (1,0) the cost is 2; entering (1,1) we arrive at t=7, which is the answer.