Problem statement

A dungeon has n x m rooms laid out as a grid. moveTime[i][j] is the earliest second at which you may start moving into room (i, j).

You are in room (0, 0) at time t = 0, and you may wait in a room as long as you like. Moves between rooms that share a wall alternate in length: your first move takes one second, the second move two seconds, the third one second again, and so on.

Return the minimum time at which you can arrive in room (n - 1, m - 1).

Example 1

Input: moveTime = [[0,4],[4,4]]
Output: 7
Explanation: Wait until t = 4 and move to (1,0) in one second (arriving at 5), then move to (1,1) in two seconds, arriving at 7.

Example 2

Input: moveTime = [[0,0,0,0],[0,0,0,0]]
Output: 6
Explanation: Four moves costing 1 + 2 + 1 + 2 seconds.

Example 3

Input: moveTime = [[0,1],[1,2]]
Output: 4

Constraints

• 2 <= n == moveTime.length <= 750
• 2 <= m == moveTime[i].length <= 750
• 0 <= moveTime[i][j] <= 10^9

Hints for Find Minimum Time to Reach Last Room II

1. Hint 1

   Every move goes to a cell whose row + column parity is the opposite of the current one, and you start on an even cell. So the length of the next move is decided by where you stand, not by how you got there.

2. Hint 2

   Leaving a cell with (i + j) even takes one second; leaving one with (i + j) odd takes two.

3. Hint 3

   Run Dijkstra on arrival times, relaxing a neighbour with max(t, moveTime[neighbour]) + cost(current cell).

How to solve Find Minimum Time to Reach Last Room II

The alternation looks like it needs the number of moves in the state, but on a grid every move flips the parity of row + column, so the move count's parity equals the current cell's parity. The cost becomes a property of the cell and plain Dijkstra applies.

Approach

1. Set time[0][0] = 0 and push it onto a min-heap.
2. Pop the cell (r, c) with the smallest time t; skip stale entries.
3. Each move out of it costs (r + c) % 2 + 1 seconds: relax every neighbour with max(t, moveTime[neighbour]) + cost.
4. Return the time of the bottom-right cell when it is popped.

Why it works

From (0, 0) (parity 0) any walk reaches a cell of parity p after a number of moves with the same parity p, so the next move's length is fixed by the cell. With that, the arrival function is non-decreasing in the departure time and adds a positive amount — the conditions Dijkstra needs.

Complexity

• Time — O(n · m · log(n · m))
• Space — O(n · m)

Pitfalls

• Do not add the move count to the state: it is unnecessary and doubles the work.
• The cost depends on the cell you leave: the first move, out of (0, 0), costs one second.
• Times reach about 10^9, so a packed heap key needs 64 bits.

Reference solution

Python

from typing import List
import heapq

def minTimeToReach(moveTime: List[List[int]]) -> int:
    n, m = len(moveTime), len(moveTime[0])
    INF = float("inf")
    dist = [[INF] * m for _ in range(n)]
    dist[0][0] = 0
    heap = [(0, 0, 0)]
    while heap:
        t, r, c = heapq.heappop(heap)
        if t > dist[r][c]:
            continue
        if r == n - 1 and c == m - 1:
            return t
        cost = (r + c) % 2 + 1
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < m:
                nt = max(t, moveTime[nr][nc]) + cost
                if nt < dist[nr][nc]:
                    dist[nr][nc] = nt
                    heapq.heappush(heap, (nt, nr, nc))
    return -1

Java

public static int minTimeToReach(int[][] moveTime) {
    int n = moveTime.length, m = moveTime[0].length, total = n * m;
    final long SH = 1048576L;
    int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};
    long[] dist = new long[total];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[0] = 0;
    PriorityQueue<Long> heap = new PriorityQueue<>();
    heap.add(0L);
    while (!heap.isEmpty()) {
        long key = heap.poll();
        int idx = (int) (key % SH);
        long t = key / SH;
        if (t > dist[idx]) continue;
        if (idx == total - 1) return (int) t;
        int r = idx / m, c = idx % m, cost = (r + c) % 2 + 1;
        for (int d = 0; d < 4; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            long nt = Math.max(t, (long) moveTime[nr][nc]) + cost;
            int ni = nr * m + nc;
            if (nt < dist[ni]) { dist[ni] = nt; heap.add(nt * SH + ni); }
        }
    }
    return -1;
}

C++

int minTimeToReach(vector<vector<int>>& moveTime) {
    int n = moveTime.size(), m = moveTime[0].size();
    int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
    vector<long long> dist(n * m, LLONG_MAX);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> heap;
    dist[0] = 0;
    heap.push(make_pair(0LL, 0));
    while (!heap.empty()) {
        long long t = heap.top().first;
        int idx = heap.top().second;
        heap.pop();
        if (t > dist[idx]) continue;
        if (idx == n * m - 1) return (int) t;
        int r = idx / m, c = idx % m, cost = (r + c) % 2 + 1;
        for (int d = 0; d < 4; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            long long nt = max(t, (long long) moveTime[nr][nc]) + cost;
            int ni = nr * m + nc;
            if (nt < dist[ni]) { dist[ni] = nt; heap.push(make_pair(nt, ni)); }
        }
    }
    return -1;
}

JavaScript

var minTimeToReach = function(moveTime) {
    var n = moveTime.length, m = moveTime[0].length, total = n * m, SH = 1048576;
    var DR = [1, -1, 0, 0], DC = [0, 0, 1, -1];
    var dist = [];
    for (var i = 0; i < total; i++) dist.push(4e12);
    dist[0] = 0;
    var heap = [0];
    while (heap.length > 0) {
        var key = heapPop(heap);
        var idx = key % SH, t = (key - idx) / SH;
        if (t > dist[idx]) continue;
        if (idx === total - 1) return t;
        var r = Math.floor(idx / m), c = idx % m, cost = (r + c) % 2 + 1;
        for (var d = 0; d < 4; d++) {
            var nr = r + DR[d], nc = c + DC[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            var nt = Math.max(t, moveTime[nr][nc]) + cost, ni = nr * m + nc;
            if (nt < dist[ni]) { dist[ni] = nt; heapPush(heap, nt * SH + ni); }
        }
    }
    return -1;
};

var heapPush = function(h, v) {
    h.push(v);
    var i = h.length - 1;
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] <= h[i]) break;
        var t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
};

var heapPop = function(h) {
    var top = h[0];
    var last = h.pop();
    if (h.length > 0) {
        h[0] = last;
        var j = 0;
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < h.length && h[l] < h[s]) s = l;
            if (r < h.length && h[r] < h[s]) s = r;
            if (s === j) break;
            var t = h[s]; h[s] = h[j]; h[j] = t;
            j = s;
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium