Problem Statement

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 after which the room opens and can be moved to. You start from the room (0, 0) at time t = 0 and can move to an adjacent room.

Moving between adjacent rooms takes:

  • 1 second for the first move.
  • 2 seconds for the second move.
  • 1 second for the third move.
  • 2 seconds for the fourth move.
  • …and so on, alternating between 1 and 2 seconds.

Return the minimum time to reach the room (n - 1, m - 1).

Two rooms are adjacent if they share a common wall (up/down/left/right).

Examples

Example 1

Input: moveTime = [[0,4],[4,4]]
Output: 7
Explanation:
- At t=0, move to (1,0) (cost 1). Arrive at t=4 (wait for 4). Next move cost will be 2.
- At t=4, wait until t=4. Move to (1,0). Wait? No, arrive t=1 (cost) + max(0, 4) = 5?
  Let's trace carefully:
  - Start (0,0) at t=0.
  - Move to (0,1): moveTime[0][1]=4. Arrive at max(0, 4) + 1 = 5. Next cost 2.
  - Move to (1,1) from (0,1): moveTime[1][1]=4. Arrive max(5, 4) + 2 = 7.
  Alternatively:
  - Start (0,0) at t=0.
  - Move to (1,0): moveTime[1][0]=4. Arrive max(0, 4) + 1 = 5. Next cost 2.
  - Move to (1,1) from (1,0): moveTime[1][1]=4. Arrive max(5, 4) + 2 = 7.

Example 2

Input: moveTime = [[0,0,0,0],[0,0,0,0]]
Output: 6
Explanation:
- (0,0) -> (0,1): cost 1. Arrive t=1.
- (0,1) -> (0,2): cost 2. Arrive t=3.
- (0,2) -> (0,3): cost 1. Arrive t=4.
- (0,3) -> (1,3): cost 2. Arrive t=6.

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

Key Insight

This is a shortest path problem on a grid where the edge weights are dynamic but depend only on the sequence of moves (1, 2, 1, 2…).

Specifically, the cost of the $k$-th move is:

  • $1$ if $k$ is odd (1st, 3rd, …)
  • $2$ if $k$ is even (2nd, 4th, …)

This creates a state (row, col, next_move_cost). Since the cost alternates between 1 and 2, next_move_cost is always either 1 or 2.

We can use Dijkstra’s Algorithm. The state in the priority queue will be {time, row, col, weight}.

  • weight is the cost to move out of the current cell to a neighbor.
  • When moving from (r, c) to (nr, nc) with weight w:
    • arrival_time = max(current_time, moveTime[nr][nc]) + w
    • The next weight for (nr, nc) will be 3 - w (swaps 1 $\to$ 2 and 2 $\to$ 1).

Solution (Dijkstra)

class Solution:
def minTimeToReach(self, moveTime):
    n = (int)len(moveTime)
    m = (int)moveTime[0].__len__()
    # dist[i][j] stores the minimum time to reach (i, j).
    # Note: strictly speaking, we might arrive at (i, j) with 'next_cost=1' or 'next_cost=2'.
    # However, arriving earlier is always better regardless of the next move cost
    # because the wait time `max(t, moveTime)` dominates small differences in edge weights.
    # A simple 2D dist array is sufficient for this problem's constraints.
    list[list[long long>> dist(n, list[long long>(m, LLONG_MAX))
    dist[0][0] = 0
    # State: :time, r, c, next_move_cost
    # next_move_cost is the cost to travel to the next neighbor.
    struct State :
    long long time
    r, c, w
    bool operator>(State other) : return time > other.time
heapq[State, list[State>, greater<>> pq
pq.push(:0, 0, 0, 1) # Start at (0,0), time 0, next move costs 1
dirs[4][2] = ::0,1, :0,-1, :1,0, :-1,0
while not not pq:
    [t, r, c, w] = pq.top()
    pq.pop()
    if (t > dist[r][c]) continue
    if (r == n - 1  and  c == m - 1) return (int)t
    for d in dirs:
        nr = r + d[0]
        nc = c + d[1]
        if (nr < 0  or  nr >= n  or  nc < 0  or  nc >= m) continue
        # Calculate arrival time at neighbor
        # Must wait until moveTime[nr][nc], then add travel cost 'w'
        long long nt = max(t, (long long)moveTime[nr][nc]) + w
        if nt < dist[nr][nc]:
            dist[nr][nc] = nt
            pq.push(:nt, nr, nc, 3 - w) # Flip weight: 1.2, 2.1
return -1 # Should not reach here

Complexity

  • Time: $O(nm \log(nm))$
  • Space: $O(nm)$

Template Reference