Easiest Solution 🔥✅ | Modified Dijkstra's
Approach\nExactly the same as:\nhttps://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/solutions/6000113/easiest-solution-heap-bfs/\nOnly differen
# Approach\nExactly the same as:\nhttps://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/solutions/6000113/easiest-solution-heap-bfs/\nOnly difference is we add a new value `check` into the heap which we will use to check if we need to add 1 or 2 to the current time. This change is made when we push again into the heap.\n\n# Complexity\n- Time complexity: $$O(m*nlog(m*n))$$, where m and n are grid dimensions.\n\n- Space complexity: $$O(m*n)$$, for the heap and visited set.\n\n# Code\n```python3 []\nclass Solution:\n    def minTimeToReach(self, moveTime: List[List[int]]) -> int:\n        m, n = len(moveTime) - 1, len(moveTime[0]) - 1\n        heap = [(0, 0, 0, True)]\n        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n        visited = set()\n        while heap:\n            time, r, c, check = heapq.heappop(heap)\n            if (r, c) == (m, n): return time\n            new = 1 if check else 2\n            for x, y in directions:\n                row, col = x + r, y + c\n                if row <= m and col <= n and col >= 0 and row >= 0 and (row, col) not in visited:\n                    heapq.heappush(heap, (max(time, moveTime[row][col]) + new, row, col, not check))\n                    visited.add((row, col))\n```\n```cpp []\n#include <vector>\n#include <queue>\n#include <tuple>\n#include <set>\nusing namespace std;\n\nclass Solution {\npublic:\n    int minTimeToReach(vector<vector<int>>& moveTime) {\n        int m = moveTime.size() - 1, n = moveTime[0].size() - 1;\n        priority_queue<tuple<int, int, int, bool>, vector<tuple<int, int, int, bool>>, greater<>> heap;\n        heap.push({0, 0, 0, true});\n        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n        set<pair<int, int>> visited;\n        while (!heap.empty()) {\n            auto [time, r, c, check] = heap.top();\n            heap.pop();\n            if (r == m && c == n) return time;\n            int newTime = check ? 1 : 2;\n            for (auto& dir : directions) {\n                int row = r + dir[0], col = c + dir[1];\n                if (row <= m && col <= n && row >= 0 && col >= 0 && !visited.count({row, col})) {\n                    heap.push({max(time, moveTime[row][col]) + newTime, row, col, !check});\n                    visited.insert({row, col});\n                }\n            }\n        }\n        return -1;\n    }\n};\n```\n```java []\nimport java.util.*;\n\nclass Solution {\n    public int minTimeToReach(int[][] moveTime) {\n        int m = moveTime.length - 1, n = moveTime[0].length - 1;\n        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);\n        heap.offer(new int[]{0, 0, 0, 1});\n        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n        Set<String> visited = new HashSet<>();\n        while (!heap.isEmpty()) {\n            int[] curr = heap.poll();\n            int time = curr[0], r = curr[1], c = curr[2], check = curr[3];\n            if (r == m && c == n) return time;\n            int newTime = check == 1 ? 1 : 2;\n            for (int[] dir : directions) {\n                int row = r + dir[0], col = c + dir[1];\n                if (row <= m && col <= n && row >= 0 && col >= 0 && !visited.contains(row + "," + col)) {\n                    heap.offer(new int[]{Math.max(time, moveTime[row][col]) + newTime, row, col, 1 - check});\n                    visited.add(row + "," + col);\n                }\n            }\n        }\n        return -1;\n    }\n}\n\n```
['Heap (Priority Queue)', 'Shortest Path', 'C++', 'Java', 'Python3']