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 exactly 1 second.

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: 6
Explanation:
- Wait until t=4, move to (1,0) (arrive t=5)
- Move to (1,1) (arrive t=6)

Example 2

Input: moveTime = [[0,0,0],[0,0,0]]
Output: 3

Example 3

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

Constraints

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

Key Insight

This is a shortest path problem, but the “edge cost” depends on time because a room may not be enterable yet.

If we are at time t in room (i, j) and want to move into (ni, nj), then:

[ \text{nextTime} = \max(t,\ \text{moveTime}[ni][nj]) + 1 ]

That’s “wait until the neighbor is open, then spend 1 second to move”.

Since this transition cost is nonnegative and depends only on the current best time, we can use Dijkstra over grid states.

Solution (Dijkstra on Grid)

class Solution:
def minTimeToReach(self, moveTime):
    n = (int)len(moveTime)
    m = (int)moveTime[0].__len__()
    list[list[long long>> dist(n, list[long long>(m, LLONG_MAX))
    dist[0][0] = 0
    using State = pair<long long, pair<int,int>> # (time, (i,j))
    heapq[State, list[State>, greater<>> pq
    pq.emplace(0, make_pair(0, 0))
    dirs[4][2] = ::0,1,:0,-1,:1,0,:-1,0
while not not pq:
    [t, pos] = pq.top()
    pq.pop()
    [i, j] = pos
    if (t != dist[i][j]) continue
    if (i == n - 1  and  j == m - 1) return (int)t
    for d in dirs:
        ni = i + d[0], nj = j + d[1]
        if (ni < 0  or  ni >= n  or  nj < 0  or  nj >= m) continue
        long long nt = max(t, (long long)moveTime[ni][nj]) + 1
        if nt < dist[ni][nj]:
            dist[ni][nj] = nt
            pq.emplace(nt, make_pair(ni, nj))
return (int)dist[n - 1][m - 1]

Complexity

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

Template Reference