# Find Minimum Time to Reach Last Room II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-minimum-time-to-reach-last-room-ii
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Matrix, Graph
---
## Problem
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 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 one second for one move and two seconds for the next, **alternating** between the two.

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:** 7

**Explanation:**

The minimum time required is 7 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 two seconds.

**Example 2:**

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

**Output:** 6

**Explanation:**

The minimum time required is 6 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 two seconds.
* At time `t == 3`, move from room `(1, 1)` to room `(1, 2)` in one second.
* At time `t == 4`, move from room `(1, 2)` to room `(1, 3)` in two seconds.

**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] <= 109`

# Approaches
## Brute-Force Depth-First Search
This approach attempts to solve the problem by exploring all possible paths from the start `(0, 0)` to the end `(n-1, m-1)` using a Depth-First Search (DFS). It's a straightforward recursive solution that tries every combination of moves. However, due to the vast number of paths in a grid, this method is computationally infeasible.
**Time:** O(4^(N*M)). In the worst case, the algorithm explores a number of paths that is exponential in the number of cells in the grid. · **Space:** O(N * M) for the recursion stack depth in the worst case, where N and M are the dimensions of the grid.
**Pros:** Conceptually simple and easy to understand as a first thought.
**Cons:** Extremely inefficient with exponential time complexity, leading to a 'Time Limit Exceeded' error for the given constraints.; A simple `visited` array is insufficient and incorrect. It prevents finding optimal paths that may need to revisit a cell. A correct brute-force would need to handle cycles without a simple visited array, making it even more complex and slower.
### Explanation
The brute-force approach uses a recursive function to explore every possible path. The state of the recursion includes the current coordinates `(r, c)`, the time elapsed `t`, and the number of moves made `m`.

Starting from `(0, 0)` at time `0` with `0` moves, the function explores all four adjacent cells. For each neighbor, it calculates the time of arrival. This depends on the current time, the `moveTime` of the neighbor cell, and the cost of the current move (1 or 2 seconds, based on the move count). It then recursively calls itself for the neighbor.

This process continues until the destination is reached, at which point the total time is compared against a global minimum. While simple in concept, this method explores a number of paths that grows exponentially with the size of the grid, making it far too slow for the given constraints. Furthermore, correctly handling paths that revisit cells is complicated and adds to the inefficiency.
### Algorithm
1. Initialize a global variable `min_time` to a very large value.
2. Define a recursive function, e.g., `dfs(row, col, currentTime, moveCount, visited)`.
3. The base case for the recursion is reaching the destination `(n-1, m-1)`. Update `min_time` with `currentTime` if it's smaller.
4. To avoid infinite loops, use a `visited` array. Mark the current cell as visited before exploring neighbors.
5. For each valid, unvisited neighbor `(nr, nc)`:
    a. Calculate the cost of the move based on `moveCount + 1`. It's `1` for an odd-numbered move and `2` for an even-numbered move.
    b. Calculate the arrival time at the neighbor: `newTime = max(currentTime, moveTime[nr][nc]) + moveCost`.
    c. Make a recursive call: `dfs(nr, nc, newTime, moveCount + 1, visited)`.
6. Backtrack by unmarking the current cell from `visited` after exploring all its neighbors.
7. Start the process by calling `dfs(0, 0, 0, 0, new boolean[n][m])`.

## Dijkstra's Algorithm with Expanded State
This problem can be efficiently solved by modeling it as a shortest path problem on a graph and using Dijkstra's algorithm. Since the cost of moving between rooms depends on the number of moves made (alternating between 1 and 2 seconds), a standard state of `(row, col)` is insufficient. We must expand the state to include the parity of the move count. This creates a new graph where each node represents `(row, col, move_parity)`, allowing Dijkstra's algorithm to find the true shortest path.
**Time:** O(N * M * log(N * M)). The number of states in our graph is `V = 2 * N * M`. Each operation on the priority queue takes `O(log V)`. We visit each state at most once. · **Space:** O(N * M), where N and M are the grid dimensions. This is for the 3D `dist` array and the priority queue, which can store up to `2*N*M` states.
**Pros:** Guaranteed to find the optimal (minimum time) solution.; Efficient enough to pass within the time limits for the given constraints.; Correctly handles all problem nuances, including the `moveTime` constraints and the alternating move costs.
**Cons:** More complex to implement compared to a standard BFS or DFS.; Requires more memory, `O(N * M)`, for the distance array and priority queue.
### Explanation
The core idea is to recognize that the cost to travel from a room `A` to a neighbor `B` is not fixed; it depends on whether it's the 1st, 2nd, 3rd, etc., move of the entire path. Specifically, it depends on the parity of the move number. This means we can arrive at the same room `(r, c)` via two different paths, and even if one path took longer, it might be preferable if it ends with a move parity that allows for cheaper subsequent moves.

To handle this, we adapt Dijkstra's algorithm. The nodes in our search space are not just the grid cells `(r, c)`, but states `(r, c, p)`, where `p` is the parity of the number of moves to reach that cell (0 for even, 1 for odd). We maintain a distance array `dist[n][m][2]` to store the minimum time to reach each of these expanded states.

A priority queue stores tuples of `[time, r, c, p]`, always allowing us to explore from the state that has the minimum time so far. When expanding from a state `(r, c, p)` with time `t`, we consider moving to a neighbor `(nr, nc)`. The new state will have parity `1-p`. The cost of this move is determined by the new parity. The arrival time at the neighbor is `max(t, moveTime[nr][nc]) + move_cost`. If this new time is an improvement for the state `(nr, nc, 1-p)`, we update its distance and add it to the priority queue. The first time we extract the destination `(n-1, m-1)` from the queue, we have found the minimum possible time.
### Algorithm
1. Define a state as `(time, row, col, parity)`, where `parity` is 0 for an even number of moves and 1 for an odd number.
2. Create a 3D distance array, `dist[n][m][2]`, to store the minimum time to reach cell `(r, c)` with a move of a certain `parity`. Initialize all entries to infinity.
3. Use a priority queue to store states `[time, row, col, parity]`, ordered by `time`.
4. Initialize `dist[0][0][0] = 0` and push the starting state `[0, 0, 0, 0]` into the priority queue.
5. While the priority queue is not empty:
    a. Extract the state `[t, r, c, p]` with the minimum time.
    b. If `t > dist[r][c][p]`, it means we've found a shorter path to this state, so skip.
    c. If `(r, c)` is the destination `(n-1, m-1)`, return `t` as it's the shortest time.
    d. For each neighbor `(nr, nc)`:
        i. The new parity is `1 - p`.
        ii. The move cost is `1` if the new parity is `1` (odd move), and `2` if it's `0` (even move).
        iii. Calculate the arrival time: `newTime = max(t, moveTime[nr][nc]) + moveCost`.
        iv. If `newTime` is less than `dist[nr][nc][1-p]`, update the distance and push the new state `[newTime, nr, nc, 1-p]` to the priority queue.

# Solutions
### Java

```java
class Solution {
public
  int minTimeToReach(int[][] moveTime) {
    int n = moveTime.length;
    int m = moveTime[0].length;
    int[][] dist = new int[n][m];
    for (var row : dist) {
      Arrays.fill(row, Integer.MAX_VALUE);
    }
    dist[0][0] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]);
    pq.offer(new int[]{0, 0, 0});
    int[] dirs = {-1, 0, 1, 0, -1};
    while (true) {
      int[] p = pq.poll();
      int d = p[0], i = p[1], j = p[2];
      if (i == n - 1 && j == m - 1) {
        return d;
      }
      if (d > dist[i][j]) {
        continue;
      }
      for (int k = 0; k < 4; k++) {
        int x = i + dirs[k];
        int y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < m) {
          int t = Math.max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1;
          if (dist[x][y] > t) {
            dist[x][y] = t;
            pq.offer(new int[]{t, x, y});
          }
        }
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minTimeToReach(vector<vector<int>> &moveTime) {
    int n = moveTime.size();
    int m = moveTime[0].size();
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    dist[0][0] = 0;
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    pq.push({0, 0, 0});
    int dirs[5] = {-1, 0, 1, 0, -1};
    while (1) {
      auto [d, i, j] = pq.top();
      pq.pop();
      if (i == n - 1 && j == m - 1) {
        return d;
      }
      if (d > dist[i][j]) {
        continue;
      }
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k];
        int y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < m) {
          int t = max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1;
          if (dist[x][y] > t) {
            dist[x][y] = t;
            pq.push({t, x, y});
          }
        }
      }
    }
  }
};

```

### Python

```python
class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int: n, m = len(moveTime), len(moveTime[0]) dist = [[inf] * m for _ in range(n)] dist[0][0] = 0 pq = [(0, 0, 0)] dirs = (- 1, 0, 1, 0, - 1) while 1: d, i, j = heappop(pq) if i == n - 1 and j == m - 1: return d if d > dist[i][j]: continue for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < n and 0 <= y < m: t = max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1 if dist[x][y] > t: dist[x][y] = t heappush(pq, (t, x, y))

```