C++ solution
2577. Minimum Time to Visit a Cell In a GridSolutionGood day, let’s tease our brain.Understanding the problemThe problem asks us to find the minimum time requir
# 2577. Minimum Time to Visit a Cell In a Grid

## Solution

Good day, let’s tease our brain.

### Understanding the problem

The problem asks us to find the minimum time required traversing from the top-left to the bottom-right, this implicitly implies the fact that we maybe using Dijkstra’s algorithm to solve this.

Different from a normal Dijkstra problem where the graph is pre-defined, that is, the weight between two connected node is a constant and would not be further modified. In this problem, there is no `fixed` distance between two node, the distance is dynamic, which is defined by the current value and the value that is to-be-traversed.

### Understanding ‘cost’ in this problem

In Dijkstra, the reason that ‘cost’ is so important because it directly affects our dicision, whether to pick this node as the next traversing node or not, whether push it or not…etc.

Well, similarly in this problem, we also wish to obtain this kind of information. But the key factor is the situation expand the possiblities of the cost required.

If the difference between `grid[r][c]` and `curr_time`

- if difference is odd, `new_time` = `grid[r][c]`
- else `new_time` = `grid[r][c]` + 1

The value that we store in the distance vector, and the given grid defines the cost of our traversing operation mutually.

### Start traversing

Note that since we are given a grid, there is no need to consturct a adjacent list or adjacent matrix, since a grid itself suffice the attrbute of a normal and viable graph.

Initially, we assume the cost requried from source to every other node is `INT_MAX`. Then, for each possible traversing option, we traverse to that node.

### Observation

there are two different sceraio: smaller or bigger. To find the required time:

case 1: `curr_time` >= `grid[r][c]`

- then `new_time` = `curr_time` + 1

case 2: `curr_time` < `grid[r][c]`

- then find difference between `grid[r][c]` and `curr_time`
- if difference is odd, `new_time` = `grid[r][c]`
- else `new_time` = `grid[r][c]` + 1

We implement this logic as follows:

```cpp
int nt = time + 1;
if (nt < grid[ni][nj]) {
    nt = grid[ni][nj];
    if ((nt - time) % 2 == 0) {
        nt++;
    }
}
```

Now, the new time variable stands for the time required if we travserse from source node to our current location, and then do further traverse to the next. If there exist an alternative distance value in distance array which represnets other value traversing from another path, which is smaller than the value that we currnetly holds, we just ignore our calculated value, since it is useless.

Conversely, if the value we possess is smaller than the value that is currently presnet in the distance array, we update the value, and further push the new node to the pq since we found another better path, it is worth explore.

Dijkstra aims to find the shortest path from the source node to the dest node, that means for each excellent path we discovered, we need to explore the possiblity of this new discovery.

### Note

Notice that once we are at the end of the grid, that means we are certainly able to return the value because the node storing in the pq is: the time required starting from top-left, i, and j. just rememeber to halt the program once this occured.

If pq is empty, that means we never reached the desired cell in the given graph, we reutrn -1.

## Code

```cpp
#define maxN 100005

using pii = pair<int, int>;
using piii = tuple<int, int, int>;

class Solution {
   public:
    int di[4] = {0, -1, 0, 1};
    int dj[4] = {-1, 0, 1, 0};
    int minimumTime(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
        vector<vector<int>> distance(n, vector<int>(m, INT_MAX));
        distance[0][0] = 0;
        priority_queue<piii, vector<piii>, greater<>> pq;
        pq.push({0, 0, 0});
        while (!pq.empty()) {
            auto [time, i, j] = pq.top();
            pq.pop();
            if (i == n - 1 && j == m - 1) {
                return time;
            }
            for (int k = 0; k < 4; k++) {
                int ni = i + di[k];
                int nj = j + dj[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= m) {
                    continue;
                }
                int nt = time + 1;
                if (nt < grid[ni][nj]) {
                    nt = grid[ni][nj];
                    if ((nt - time) % 2 == 0) {
                        nt++;
                    }
                }
                if (nt < distance[ni][nj]) {
                    distance[ni][nj] = nt;
                    pq.push({nt, ni, nj});
                }
            }
        }
        return -1;
    }
};
```

['C++']