Minimum Time to Traverse Grid with Alternating Costs Using Dijkstra's Algorithm using visited array
IntuitionThe problem requires finding the minimum time to traverse a grid where each cell represents a waiting time, and moves alternate between a cost of 1 and
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires finding the minimum time to traverse a grid where each cell represents a waiting time, and moves alternate between a cost of 1 and 2 units. This can be solved using a modified version of Dijkstra's shortest path algorithm, as it efficiently handles weighted grids.
# Approach
<!-- Describe your approach to solving the problem. -->
State Representation: Each state in the priority queue is represented as (current_time, {x, y, alternating_flag}), where:

current_time is the time taken to reach the current cell.
(x, y) is the current cell position.
alternating_flag indicates whether the next move costs 1 or 2 units.
Priority Queue:

The priority queue ensures that we always process the state with the smallest current_time first.
Push (time, {x, y, flag}) into the queue only if it improves the minimum time for the cell.
Direction Vector:

Use dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}} to represent all four possible directions (up, down, left, right).
Update Mechanism:

For each neighbor (nx, ny) of the current cell (x, y), calculate the new time:
If grid[nx][ny] is less than or equal to current_time, proceed immediately.
Otherwise, wait until grid[nx][ny] and then move.
Visited Array:

Maintain a 2D vis array to ensure cells are not revisited unnecessarily, which optimizes the solution.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(n×m×log(n×m))


- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n×m)
# Code
```cpp []
class Solution {
    #define pip pair<int, pair<bool, pair<int,int>>> 

    bool isValid(int n, int m, int newX, int newY, vector<vector<bool>>& vis) {
        return newX >= 0 && newX < n && newY >= 0 && newY < m && !vis[newX][newY];
    }

public:
    int minTimeToReach(vector<vector<int>>& mt) {
        vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int n = mt.size(), m = mt[0].size();
        priority_queue<pip, vector<pip>, greater<pip>> pq;
        vector<vector<bool>> vis(n, vector<bool>(m, false));
        pq.push({0,{true, {0, 0}}});

        while (!pq.empty()) {
            int x = pq.top().second.second.first;
            int y = pq.top().second.second.second;
            bool check=pq.top().second.first;
            int time = pq.top().first;
            pq.pop();

            if (x == n - 1 && y == m - 1) {
                return time;
            }
            if (vis[x][y]) continue;
            vis[x][y]=true;
            for (int i = 0; i < 4; i++) {
                int newX = x + dirs[i][0];
                int newY = y + dirs[i][1];

                if (isValid(n, m, newX, newY, vis)) {
                    int newTime = mt[newX][newY];
                    int toAdd = check ? 1 : 2;
                    if (newTime <= time) {
                        pq.push({time + toAdd,{!check, {newX, newY}}});
                    } else {
                        pq.push({newTime + toAdd,{!check, {newX, newY}}});
                    }
                    
                }
            }
            
            
        }

        return -1;
    }
};

```
['Array', 'Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'C++']