Minimum Time To Reach Last Room II !100% Beat CPP
Intuition\n\nThe problem at hand seems to be a pathfinding challenge where you need to calculate the minimum time to traverse a grid, starting from the top-left
### Intuition\n\nThe problem at hand seems to be a pathfinding challenge where you need to calculate the minimum time to traverse a grid, starting from the top-left corner `(0, 0)` and ending at the bottom-right corner `(m-1, n-1)`. Each cell in the grid has a "time" value that could affect your movement through it. The grid might involve alternating movement times (e.g., even steps could take 1 second, odd steps could take 2 seconds) and may require you to wait at certain cells until a specific time. A **priority queue** can be used to explore cells in order of the least time taken to reach them, which is similar to Dijkstra\u2019s shortest path algorithm, with slight modifications to account for the alternating time and waiting periods.\n\n### Approach\n\n1. **Grid Representation**: \n   - The grid is a 2D vector where each element contains a value that represents a "time" or some kind of condition to move through that cell.\n   \n2. **Priority Queue for Efficient Pathfinding**:\n   - Use a **priority queue** (min-heap) to process the cells in order of the least time required to reach them. This is akin to Dijkstra\u2019s algorithm where we always process the current shortest time first.\n   - The priority queue stores tuples of `(step, time, cell)`, where:\n     - `step` indicates whether we are in an even or odd step (affecting movement time).\n     - `time` is the current time at the cell.\n     - `cell` is the linearized position of the grid (to easily handle 2D grid access).\n   \n3. **Movement Calculation**:\n   - The four possible directions are represented by a list of pairs `directions = [(1,0), (0,1), (-1,0), (0,-1)]`.\n   - Each direction corresponds to a movement in the grid (right, down, left, up).\n\n4. **State Updates**:\n   - For each neighboring cell, compute the new time considering:\n     - The current time (whether it\'s even or odd step).\n     - Whether we need to wait (if the current time is less than the grid value at the neighbor).\n     - The movement time, which alternates between 1 and 2 seconds based on the `step`.\n\n5. **Priority Queue Push**:\n   - If a new time for a neighboring cell is better (smaller) than the previously recorded time, update the time and push the new state (updated time, step, position) into the priority queue.\n\n6. **Termination**:\n   - The process continues until we reach the destination cell `(m-1, n-1)`, and the corresponding time is returned.\n\n### Complexity\n\n- **Time complexity**:\n  - The algorithm is based on Dijkstra\u2019s shortest path, so the time complexity is proportional to the number of cells (nodes) in the grid and the number of edges (possible directions).\n  - Since we use a priority queue, each insertion and extraction takes logarithmic time.\n  - Therefore, the time complexity is **O((m * n) * log(m * n))**, where `m * n` is the number of cells in the grid.\n\n- **Space complexity**:\n  - We maintain a `time` 2D array to track the minimum time to reach each cell, and we use a priority queue that stores each cell at least once.\n  - The space complexity is **O(m * n)** for the `time` array and the priority queue.\n\n### Code Explanation\n\n```cpp\nauto speedUp = []() {\n    ios_base::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return 0;\n}();\n#define p pair< int, pair<int,int> >  // {step {time, cell}}\n```\n- This snippet optimizes input/output operations to make the program run faster for larger inputs.\n- The macro `p` defines a tuple type to represent a state in the priority queue: `{step, {time, cell}}`.\n\n---\n\n```cpp\nclass Solution {\npublic:\n    int minTimeToReach(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n```\n- Here, `m` and `n` represent the number of rows and columns in the grid.\n\n---\n\n```cpp\n        vector<pair<int,int>> directions = { {1,0}, {0,1}, {-1,0}, {0,-1} };\n```\n- This vector stores the four possible directions (right, down, left, up) for movement in the grid.\n\n---\n\n```cpp\n        vector<vector<int>> time(m, vector<int>(n, INT_MAX));\n        time[0][0] = 0;\n```\n- The `time` array keeps track of the minimum time required to reach each cell.\n- We initialize all cells with `INT_MAX` (infinity), except for the starting cell `(0, 0)` which is set to `0` because no time is required to be there initially.\n\n---\n\n```cpp\n        priority_queue<p, vector<p>, greater<p>> pq;\n        pq.push({0, {0, 0}});\n```\n- We initialize the priority queue `pq` which will store states in the form of `(step, {time, cell})`. We push the starting cell `(0,0)` with time `0`.\n\n---\n\n```cpp\n        while (!pq.empty()) {\n            p top = pq.top();\n            pq.pop();\n            int step = top.first;\n            int curr_time = top.second.first;\n            int row = top.second.second / n;\n            int col = top.second.second % n;\n```\n- The main loop processes the room with the least time, popping it from the priority queue.\n- We extract `step`, `curr_time`, `row`, and `col` from the current state.\n\n---\n\n```cpp\n            if (row == m - 1 && col == n - 1) \n                return curr_time;\n```\n- If we reach the bottom-right corner, we return the current time as the result.\n\n---\n\n```cpp\n            for (auto& dir : directions) {\n                int nr = row + dir.first;\n                int nc = col + dir.second;\n                if (nr < 0 || nr >= m || nc < 0 || nc >= n) \n                    continue;\n```\n- We iterate over the four possible directions to move to the neighboring cells.\n- If the new position is out of bounds, we skip it.\n\n---\n\n```cpp\n            // Calculate the next time\n            int move_time = curr_time % 2 == 0 ? 1 : 2; // Alternates: 1s -> 2s\n            int wait_time = max(0, grid[nr][nc] - curr_time);\n            int new_time = curr_time + move_time + wait_time;\n```\n- We calculate the `move_time` based on whether the current time is even or odd.\n- The `wait_time` is calculated if the current time is less than the grid value at the neighboring cell, meaning we need to wait for the appropriate time to move there.\n\n---\n\n```cpp\n            if (new_time < time[nr][nc]) {\n                time[nr][nc] = new_time;\n                pq.push({step == 0 ? 1 : 0, {new_time, nr * n + nc}});\n            }\n        }\n        return -1;\n    }\n};\n```\n- If the `new_time` to reach the neighboring cell is better than the previously stored time, we update the `time` array and push the new state into the priority queue with the updated `step` and `time`.\n\n- If the queue is exhausted without reaching the destination, we return `-1` as a fallback.\n\n---\n### Code\n```cpp []\nauto speedUp = []() {\n    ios_base::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return 0;\n}();\n#define p pair< int, pair<int,int> >\n\nclass Solution {\npublic:\n    int minTimeToReach(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n\n        vector<pair<int,int>> directions = { {1,0}, {0,1}, {-1,0}, {0,-1} };\n\n        vector<vector<int>> time(m, vector<int> (n, INT_MAX));\n        time[0][0] = 0;\n\n        priority_queue< p, vector<p>, greater<p> > pq;\n        pq.push({0, {0,0}}); // {step, time, cell}\n\n        while(!pq.empty()){\n            p top = pq.top();\n            pq.pop();\n            int step = top.first;\n            int curr_time = top.second.first;\n            int row = top.second.second / n;\n            int col = top.second.second % n;\n\n            if(row == m-1 && col == n-1) return curr_time;\n            for(auto &dir : directions){\n                int nr = row + dir.first;\n                int nc = col + dir.second;\n\n                if( nr == -1 || nr == m || nc == -1 || nc == n ) continue;\n                int new_time;\n\n                if(step == 0){\n                    if(curr_time >= grid[nr][nc]) new_time = curr_time + 1;\n                else new_time = grid[nr][nc] + 1;\n                }else{\n                    if(curr_time >= grid[nr][nc]) new_time = curr_time + 2;\n                else new_time = grid[nr][nc] + 2;\n                }\n                \n                if(new_time < time[nr][nc]){\n                    time[nr][nc] = new_time;\n                    pq.push({step==0 ? 1 : 0, {new_time, nr*n + nc}});\n                }\n            }\n        }\n        return -1;        \n    }\n};\n```\n### Conclusion\n\nThis approach effectively uses a modified Dijkstra\'s algorithm with a priority queue to find the minimum time to reach the bottom-right corner of the grid, considering alternating movement times and potential wait times at certain cells. The time and space complexities are optimal for this type of problem.
['Array', 'Graph', 'Heap (Priority Queue)', 'Shortest Path', 'C++']