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.

Thinking Process

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.

  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
  • Union-Find helps when connectivity updates are frequent.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
BFS / DFS traversal O(V+E) O(V) Connectivity, flood fill
Dijkstra O((V+E)log V) O(V) Non-negative edge weights
Union-Find (DSU) (this problem) O(α(n)) O(n) Dynamic connectivity
Topological sort O(V+E) O(V) DAG ordering, cycle detection

Solution

import heapq

class Solution:
    def minTimeToReach(self, moveTime):
        n, m = len(moveTime), len(moveTime[0])
        
        INF = float('inf')
        dist = [[INF] * m for _ in range(n)]
        dist[0][0] = 0
        
        # (time, i, j)
        pq = [(0, 0, 0)]
        
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        while pq:
            t, i, j = heapq.heappop(pq)
            
            if t != dist[i][j]:
                continue
            
            if i == n - 1 and j == m - 1:
                return t
            
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                
                if ni < 0 or ni >= n or nj < 0 or nj >= m:
                    continue
                
                nt = max(t, moveTime[ni][nj]) + 1
                
                if nt < dist[ni][nj]:
                    dist[ni][nj] = nt
                    heapq.heappush(pq, (nt, ni, nj))
        
        return dist[n - 1][m - 1]

Solution Explanation

Approach: Union-Find (DSU) (this problem)

Key idea: There is a dungeon with n x m rooms arranged as a grid.

How the code works:

  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
  • Union-Find helps when connectivity updates are frequent.

    Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • Pattern: Union-Find (DSU) (this problem)
  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.

References

Template Reference