Problem Informations

Problem Index: 3341
Problem Link: Find Minimum Time to Reach Last Room I
Topics: Array, Graph, Heap (Priority Queue), Matrix, Shortest Path

Problem Description

There is a dungeon with $n \times m$ rooms arranged as a grid.

You are given a 2D array moveTime of size $n \times m$, where moveTime[i][j] represents the minimum time in seconds when you can start moving to that room. You start from the room (0, 0) at time $t = 0$ and can move to an adjacent room. Moving between adjacent rooms takes exactly one second.

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

Two rooms are adjacent if they share a common wall, either horizontally or vertically.

Example 1:

Input: moveTime = [[0,4],[4,4]]

Output: 6

Explanation:

The minimum time required is 6 seconds.

At time $t == 4$, move from room (0, 0) to room (1, 0) in one second.
At time $t == 5$, move from room (1, 0) to room (1, 1) in one second.

Example 2:

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

Output: 3

Explanation:

The minimum time required is 3 seconds.

At time $t == 0$, move from room (0, 0) to room (1, 0) in one second.
At time $t == 1$, move from room (1, 0) to room (1, 1) in one second.
At time $t == 2$, move from room (1, 1) to room (1, 2) in one second.

Example 3:

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

Output: 3

Constraints:

$2 \leq n == \text{moveTime.length} \leq 50$
$2 \leq m == \text{moveTime[i].length} \leq 50$
$0 \leq \text{moveTime[i][j]} \leq 10^{9}$

Intuition

The problem requires calculating the minimum time to reach a specific room in a grid layout where each cell has a minimum time constraint before it can be entered. This resembles a pathfinding problem with specific timing constraints on each node. The challenge entails navigating from the top-left to the bottom-right, adhering to these constraints. The natural solution involves exploring the grid while optimizing the traverse time and obeying the timing rules for entering each cell.

Approach

We can solve this problem using a priority queue to facilitate a Dijkstra-like algorithm, which efficiently handles the time constraints and enables us to prioritize paths with potentially lower travel times. Here is the detailed approach:

Data Structure Initialization:
Initialize a priority queue (min-heap) to manage cells based on their cumulative travel time in ascending order, ensuring the cell with the shortest time is processed next. This allows for optimal path exploration. Also, create a 2D boolean array to track visited cells, preventing redundant processing and infinite loops.
Priority Queue Setup:
Begin by adding the starting cell (0, 0) with an initial time of 0 to the priority queue. The priority queue will maintain tuples of the form (current_time, (row, column)).
Exploration Loop:
Use a loop to process cells until the queue is empty:
- Extract the cell with the minimum time from the priority queue.
- If this cell is the destination (n-1, m-1), return its time as the answer.
- Mark the current cell as visited.
- Explore all neighboring cells (up, down, left, right). For each neighbor:
  - Verify that the cell is inside the grid bounds and not previously visited.
  - Calculate the time needed to move to this cell: it’s the maximum of the current cell’s time and this cell’s move-start time, plus one second for the move.
  - Insert these neighboring cells into the priority queue with their calculated move time. Use negative values to implement a min-heap using the standard C++ priority queue, which is a max-heap by default.
Termination and Edge Cases:
If the priority queue is exhausted without reaching the destination, return -1 (indicating the destination is unreachable, though this scenario is unlikely with the given problem constraints).

By adhering to this priority-driven exploration strategy, we ensure that we always extend paths with the lowest travel time, effectively managing the constraints and efficiently solving the problem.

Code

C++

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size();  // Number of rows
        int m = moveTime[0].size();  // Number of columns
        vector<vector<bool>> visited(n, vector<bool>(m, false));  // Visited rooms tracker
        int moves[] = {1, 0, -1, 0, 1};  // Direction vectors for moving up, right, down, left
        priority_queue<pair<int, pair<int, int>>> pq;  // Min-heap priority queue

        // Start with the initial room (0, 0) at time 0
        pq.push({0, {0, 0}});

        while (!pq.empty()) {
            // Get the current room and time
            pair<int, pair<int, int>> cur_pair = pq.top();
            pq.pop();
            int cur_y = cur_pair.second.first;  // Current row
            int cur_x = cur_pair.second.second;  // Current column

            // Skip if already visited
            if (visited[cur_y][cur_x]) continue;

            // Mark the current room as visited
            visited[cur_y][cur_x] = true;

            // If the target room (n-1, m-1) is reached, return the time
            if (cur_y == n - 1 && cur_x == m - 1) return -cur_pair.first;

            // Explore adjacent rooms
            for (int i = 0; i < 4; i++) {
                int nxt_y = cur_y + moves[i];  // Next row
                int nxt_x = cur_x + moves[i + 1];  // Next column

                // Check if the next room is within bounds
                if (nxt_y < 0 || nxt_y >= n || nxt_x < 0 || nxt_x >= m) continue;

                // Add the next room to the priority queue with the updated time
                pq.push({-max(-cur_pair.first, moveTime[nxt_y][nxt_x]) - 1, {nxt_y, nxt_x}});
            }
        }

        return -1;  // Return -1 if the target room cannot be reached (unlikely with valid input)
    }
};

Python

from heapq import heappush, heappop

class Solution:
    def minTimeToReach(self, moveTime):
        n = len(moveTime)  # Number of rows
        m = len(moveTime[0])  # Number of columns
        visited = [[False] * m for _ in range(n)]  # Visited rooms tracker
        moves = [1, 0, -1, 0, 1]  # Direction vectors for moving up, right, down, left
        pq = []  # Min-heap priority queue

        # Start with the initial room (0, 0) at time 0
        heappush(pq, (0, 0, 0))

        while pq:
            # Get the current room and time
            cur_time, cur_y, cur_x = heappop(pq)

            # Skip if already visited
            if visited[cur_y][cur_x]:
                continue

            # Mark the current room as visited
            visited[cur_y][cur_x] = True

            # If the target room (n-1, m-1) is reached, return the time
            if cur_y == n - 1 and cur_x == m - 1:
                return -cur_time

            # Explore adjacent rooms
            for i in range(4):
                nxt_y = cur_y + moves[i]  # Next row
                nxt_x = cur_x + moves[i + 1]  # Next column

                # Check if the next room is within bounds
                if nxt_y < 0 or nxt_y >= n or nxt_x < 0 or nxt_x >= m:
                    continue

                # Add the next room to the priority queue with the updated time
                heappush(pq, (-max(-cur_time, moveTime[nxt_y][nxt_x]) - 1, nxt_y, nxt_x))

        return -1  # Return -1 if the target room cannot be reached (unlikely with valid input)

Complexity

Time complexity: The time complexity is approximately $O(n \cdot m \cdot \log(n \cdot m))$. This is because, in the worst case, each room in the $n \times m$ grid will be processed once, and each operation of insertion or extraction in the priority queue (min-heap) will take $O(\log(n \cdot m))$. Therefore, the overall complexity is approximately bounded by $O(n \cdot m \cdot \log(n \cdot m))$.
Space complexity: The space complexity is $O(n \cdot m)$, which accounts for the space required to maintain the visited array and the priority queue, which can store up to $n \cdot m$ elements in the worst case.

CS Note
中

Leetcode 3341. Find Minimum Time to Reach Last Room I