Easy Solution in C++
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve the problem of finding the minimum time to traverse a grid while waiting for c
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve the problem of finding the minimum time to traverse a grid while waiting for certain cells to become accessible, we can think of this as a pathfinding problem on a weighted graph. Each cell in the grid can be viewed as a node, and the edges between nodes correspond to possible movements (up, down, left, right). The challenge arises from the fact that some cells can only be accessed at specific times, which adds a layer of complexity to the traversal\n# Approach\n<!-- Describe your approach to solving the problem. -->\nGrid Representation: The grid is represented as a 2D vector where each cell contains the time at which it becomes accessible.\n\nPriority Queue: We will use a min-heap (priority queue) to always expand the least time-consuming path first. This allows us to implement a modified version of Dijkstra\'s algorithm.\n\nInitialization: Start from the top-left corner of the grid (0, 0) with an initial time of 0. Push this position onto the priority queue.\n\nTraversal: While the priority queue is not empty:\n\nExtract the cell with the minimum time.\nIf this cell is the bottom-right corner of the grid, return the current time as the minimum time to reach the destination.\nFor each possible move (up, down, left, right), calculate the next cell\'s time:\nIf the current time is less than the time required to enter the next cell, calculate the waiting time.\nPush the new position and the calculated time into the priority queue if it hasn\'t been visited yet.\nVisited Tracking: Use a 2D vector to keep track of visited cells to prevent processing the same cell multiple times.\n\nEdge Case Handling: If both the right and down cells from the starting position are blocked initially (i.e., they require a time greater than 1), return -1 immediately since it\'s impossible to move.\n# Complexity\nTime complexity: The time complexity of this approach is (O(V \\log V)), where (V) is the number of cells in the grid (i.e., (rows \\times cols)). Each cell can be added to the priority queue once, and extracting the minimum from the priority queue takes logarithmic time.\n\nSpace complexity: The space complexity is (O(V)) due to the storage required for the priority queue and the visited array, where (V) is the number of cells in the grid.\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;\n        \n        int rows = grid.size();\n        int cols = grid[0].size();\n        \n        priority_queue<pair<int, pair<int, int>>, \n                      vector<pair<int, pair<int, int>>>, \n                      greater<pair<int, pair<int, int>>>> minHeap;\n        \n        minHeap.push({0, {0, 0}});\n        \n        vector<vector<int>> seen(rows, vector<int>(cols, 0));\n        seen[0][0] = 1;\n        \n        vector<pair<int, int>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n        \n        while (!minHeap.empty()) {\n            auto curr = minHeap.top();\n            int currTime = curr.first;\n            int currRow = curr.second.first;\n            int currCol = curr.second.second;\n            \n            minHeap.pop();\n            \n            if (currRow == rows - 1 && currCol == cols - 1) \n                return currTime;\n            \n            for (auto move : moves) {\n                int nextRow = move.first + currRow;\n                int nextCol = move.second + currCol;\n                \n                if (nextRow >= 0 && nextCol >= 0 && \n                    nextRow < rows && nextCol < cols && \n                    !seen[nextRow][nextCol]) {\n                    \n                    int waitTime = ((grid[nextRow][nextCol] - currTime) % 2 == 0) ? 1 : 0;\n                    int nextTime = max(currTime + 1, grid[nextRow][nextCol] + waitTime);\n                    \n                    minHeap.push({nextTime, {nextRow, nextCol}});\n                    seen[nextRow][nextCol] = 1;\n                }\n            }\n        }\n        return -1;\n    }\n};\n```
['Array', 'Breadth-First Search', 'Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'C++']