Problem Overview: Navigating a Time-Locked Dungeon Grid

Imagine you're trapped in a dungeon that looks like a grid. Each cell in the grid represents a room. Some rooms are instantly accessible, while others are locked and only become accessible after a certain time.

You're placed in the top-left corner of the grid at time zero. From there, your goal is to reach the bottom-right corner as quickly as possible. You can move in four directions up, down, left, or right and each movement takes exactly one second.

However, there’s a catch: you can only enter a room after its unlock time, defined in a 2D array called moveTime. This array tells you the earliest time each room becomes available. If you reach a room before it’s ready, you’ll have to wait until it unlocks.

So this isn’t just a shortest-path problem. It's a time-constrained navigation problem, where you may have to wait or take detours to find the quickest path to the goal. Your mission is to calculate the minimum time required to reach the bottom-right room while obeying all the unlock delays.

This problem introduces an interesting twist to classic pathfinding one where movement depends on time, not just distance.

What Is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is a popular method for finding the shortest path from a starting point to all other points in a graph, especially when edges have different costs.

The key idea is simple:

Always expand the node that can be reached with the smallest cost so far.
Use a priority queue to keep track of which node to visit next.
Update the shortest known distance (or time) to each node only if the new path is faster.

Why does this matter here?

In our dungeon grid, the “cost” isn’t distance it’s time, and sometimes we must wait to enter a room. So instead of tracking distance, we track earliest arrival time to each cell, and Dijkstra’s logic helps us always make the most efficient move next.

If you'd like to explore Dijkstra's algorithm in more detail or see how it works visually, here are two excellent resources:

In-Depth Article: GeeksforGeeks - Dijkstra’s Shortest Path Algorithm (Greedy)
Interactive Visualization: USF Dijkstra's Algorithm Visualizer

Step-by-Step Solution Breakdown

Now that we understand the problem and the logic behind Dijkstra’s algorithm, let's walk through the solution in Python.

1. Initial Setup

import heapq

def minTimeToReach(moveTime):
    n, m = len(moveTime), len(moveTime[0])
    time = [[float('inf')] * m for _ in range(n)]
    time[0][0] = moveTime[0][0]
    heap = [(0, 0, 0)]  # (current_time, x, y)

We start by importing heapq (note: not required on LeetCode) to use a min-heap (priority queue), which ensures we always process the room that can be reached the earliest.

Then, we initialize a 2D array time to track the earliest known time to reach each room. All cells are initially set to infinity, except the starting room (0, 0), which is reachable at its own unlock time.

3. Exploring Neighboring Cells

    for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < m:

For each step, we explore the four possible directions: right(0, 1) , down(1, 0), left(0, -1), and up(-1, 0).
We also make sure the new coordinates (nx, ny) are inside the grid boundaries.

4. Calculating the Time to Enter the Next Room

                if moveTime[nx][ny] > t:
                    nt = moveTime[nx][ny] + 1
                else:
                    nt = t + 1

Here’s the heart of the logic. If the next room hasn’t unlocked yet (moveTime[nx][ny] > t), we wait until it’s unlocked, then add 1 second to move.
If it’s already unlocked, we simply move in after 1 second.

5. Updating and Pushing New State

                if nt < time[nx][ny]:
                    time[nx][ny] = nt
                    heapq.heappush(heap, (nt, nx, ny))

If the time nt to reach (nx, ny) is better than any time we’ve seen before, we update it and add this state to the heap to explore it later.
This ensures we’re only following faster paths, ignoring slower ones.

Final Thoughts

This problem is a fantastic example of how classic algorithms like Dijkstra’s can be adapted to solve modern, constraint-based pathfinding challenges.

Thanks for reading!

Feel free to leave a comment or question if you found this helpful or want to dive deeper into similar problems.

LeetCode Problem 3341: Find Minimum Time to Reach Last Room