Looks like a simple `bfs` would work? Hmm..let's optimize it. 
IntuitionLooks like a simple bfs would work? Hmm..let's optimize it.ApproachIf you are at a cell say x with Tx time, you can move to an adjacent cell y with Ty
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Looks like a simple `bfs` would work? Hmm..let's optimize it. 
# Approach
<!-- Describe your approach to solving the problem. -->
If you are at a cell say `x` with `Tx` time, you can move to an adjacent cell `y` with `Ty` time
 with the following cases
  1. If you reached early than the required wait time, you will have to wait atleast `Ty`.
  2. If reached on time/later than `Ty`, you can move at no cost...apart from the move cost (1 or 2). 
   
   [x] -> [y]
  So the new time to move from cell [x] to cell [y] would be 
  ```
int newTime = moveCost + max(Tx, Ty);
```
that's it, put this into `bfs` & it will **TLE**  :)

Now let's optimize: 

Suppose you can reach cell `[x] -> [y] in time 4` via some path, so you update the adjacent cells of `[y]` accordingly and so on. Now suppose you figured out another path you can reach the cell `[x] -> [y] in time 3` (**less than 4**)...now you will have to update all the adjacents of `[y]` again as per the min time of 3, `so the previous updates with time of 4 were of no use`.

We could have avoided it....

One would use a simple `Queue` for `bfs`. But...What is out goal? to get the minimum time to reach any cell from (0, 0) so shouldn't we try to pick the one with the minimum time from the `Queue` first and avoid processing the once if for some node the min reach time is already less than the calculated `newTime`?

So we use `priority_queue(min heap)` instead.

Basically, wou would want to know the path that led to the `time of 3 in reaching [y]` first so you can `avoid the processing as per the time of 4 in reaching [y]`

```
int newTime = add + max(A[xx][yy], time);
if (newTime < minTime[xx][yy]) {
    minTime[xx][yy] = newTime;
    q.push(Room(xx, yy, newTime, ((add == 1) ? 2 : 1)));
}
```

And ladies & gentleman it's **`Dijkstra’s shortest path algorithm`**

# Complexity
- Time complexity:
For each node you will have 4 neighbours, so complexity: n\*m\*4 ~ `O(n*m)` ...nahh...dont's forget the heap
so it becomes : `O((nm)⋅log(nm))`

- Space complexity:
Size of input: `O(n*m)`

# Code
```cpp []
class Solution {
    struct Room {
        int x;
        int y;
        int time;
        int add;

        Room(int xx, int yy, int ttime, int aadd) {
            x = xx;
            y = yy;
            time = ttime;
            add = aadd;
        }
    };

    struct CompareTask {
        bool operator()(const Room& t1, const Room& t2) {
            return t1.time >
                   t2.time; // Min-heap (smallest priority first)
        }
    };

public:
    int minTimeToReach(vector<vector<int>>& A) {
        int n = A.size();
        int m = A[0].size();

        vector<vector<int>> minTime(n, vector<int>(m, INT_MAX));
        int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        priority_queue<Room, vector<Room>, CompareTask> q;

        q.push(Room(0, 0, 0, 1));

        while (!q.empty()) {
            Room top = q.top();
            int x = top.x;
            int y = top.y;
            int time = top.time;
            int add = top.add;

            q.pop();

            for (int i = 0; i < 4; i++) {
                int xx = x + dir[i][0];
                int yy = y + dir[i][1];

                if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
                    int newTime = add + max(A[xx][yy], time);
                    if (newTime < minTime[xx][yy]) {
                        minTime[xx][yy] = newTime;
                        q.push(Room(xx, yy, newTime, ((add == 1) ? 2 : 1)));
                    }
                }
            }
        }

        return minTime[n - 1][m - 1];
    }
};
```
['C++']