[Python3/C++/Java] Dijkstra - Detailed Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n- Shortest Path with a lot of constraints and conditions\n- All parameters are posivite
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Shortest Path with a lot of constraints and conditions\n- All parameters are posivite\n- It is the signal of Dijkstra or BFS\n- Each going path has its own weight. Thus Dijkstra\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Problem Understanding**\n\n- `moveTime`: A 2D list representing a grid. Each cell `moveTime[i][j]` holds the time it takes to move into that cell.\n- The goal is to start at the top-left corner `(0, 0)` and reach the bottom-right corner `(m-1, n-1)` in the minimum possible time.\n- There\'s a catch: after moving into a cell with a move time of `1`, the next move takes 2 units of time, and the next of next move takes 2 unit of times, and so on.\n\n**Code Explanation**\n\n**1. Initialization**:\n\n - `m, n = len(moveTime), len(moveTime[0])`: Get the dimensions of the grid.\n- `min_time`: A 2D list to store the minimum time to reach each cell. Initialized with infinity `float("inf")` for all cells except the starting cell `(0, 0)`, which is set to `0`.\n- `pq`: A priority queue (using `heapq`) to store tuples of `(current_time, i, j, move_time)`. This queue helps explore the grid efficiently by prioritizing cells with shorter travel times. It\'s initialized with the starting cell.\n\n**2. Dijkstra\'s Algorithm with a Twist**:\n\n- The code essentially uses a modified Dijkstra\'s algorithm. It iteratively explores the grid, expanding from the cell with the current minimum time.\n- `while pq:`: The loop continues as long as there are cells to explore in the priority queue.\n    - `cur_time, i, j, move_time = heapq.heappop(pq)`: Get the cell with the smallest cur_time from the queue.\n    - `if i == m - 1 and j == n - 1: return cur_time`: If the current cell is the destination, return the `cur_time`.\n    - `new_move_time = 2 if move_time == 1 else 1`: Calculate the move time for the next step based on the current `move_time`.\n    - `for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:`: Explore the four neighboring cells (up, down, left, right).\n        - `ni, nj = i + di, j + dj`: Calculate the coordinates of the neighbor.\n        - `if ni < 0 or ni == m or nj < 0 or nj == n: continue`: Skip if the neighbor is out of bounds.\n        - `new_time = max(cur_time, moveTime[ni][nj]) + new_move_time:` Calculate the time to reach the neighbor. It\'s the maximum of the current time and the move time of the neighbor cell, plus the `new_move_time`.\n        - `if min_time[ni][nj] > new_time`: If this new time is shorter than the current minimum time to reach the neighbor, update `min_time` and add the neighbor to the priority queue.\n\n- `Return -1`: If the loop finishes without finding a path to the destination (which shouldn\'t happen in this scenario), the code returns -1.\n\n**In Summary**\n\nThis code efficiently finds the minimum time to navigate a grid with varying move times between cells. It uses a priority queue to prioritize exploration and a modified Dijkstra\'s algorithm to find the shortest path based on the time constraints.\n\n# Complexity\n- Time complexity: $$O(N * M log(N * M))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N * M)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minTimeToReach(self, moveTime: List[List[int]]) -> int:\n        m, n = len(moveTime), len(moveTime[0])\n        min_time = [[float("inf") for _ in range(n)] for _ in range(m)]\n        min_time[0][0] = 0\n        pq = [(0, 0, 0, 2)]\n        while pq:\n            cur_time, i, j, move_time = heapq.heappop(pq)\n            if i == m - 1 and j == n - 1: return cur_time\n            new_move_time = 2 if move_time == 1 else 1\n            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n                ni, nj = i + di, j + dj\n                if ni < 0 or ni == m or nj < 0 or nj == n: continue\n                new_time = max(cur_time, moveTime[ni][nj]) + new_move_time\n                if min_time[ni][nj] > new_time:\n                    min_time[ni][nj] = new_time\n                    heapq.heappush(pq, (new_time, ni, nj, new_move_time))\n        return -1\n```\n```C++ []\nclass Solution {\npublic:\n    int minTimeToReach(vector<vector<int>>& moveTime) {\n        int m = moveTime.size();\n        int n = moveTime[0].size();\n        vector<vector<int>> min_time(m, vector<int>(n, numeric_limits<int>::max()));\n        min_time[0][0] = 0;\n        priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> pq;\n        pq.push({0, 0, 0, 2}); \n\n        while (!pq.empty()) {\n            auto [cur_time, i, j, move_time] = pq.top();\n            pq.pop();\n            if (i == m - 1 && j == n - 1) return cur_time;\n            int new_move_time = (move_time == 1) ? 2 : 1;\n            for (auto [di, dj] : vector<pair<int, int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {\n                int ni = i + di, nj = j + dj;\n                if (ni < 0 || ni == m || nj < 0 || nj == n) continue;\n                int new_time = max(cur_time, moveTime[ni][nj]) + new_move_time;\n                if (min_time[ni][nj] > new_time) {\n                    min_time[ni][nj] = new_time;\n                    pq.push({new_time, ni, nj, new_move_time});\n                }\n            }\n        }\n        return -1;\n    }\n};\n```\n``` java[]\nclass Solution {\n    public int minTimeToReach(int[][] moveTime) {\n        int m = moveTime.length;\n        int n = moveTime[0].length;\n        int[][] min_time = new int[m][n];\n        for (int i = 0; i < m; i++) {\n            Arrays.fill(min_time[i], Integer.MAX_VALUE);\n        }\n        min_time[0][0] = 0;\n        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); \n        pq.offer(new int[]{0, 0, 0, 2}); \n\n        while (!pq.isEmpty()) {\n            int[] entry = pq.poll();\n            int cur_time = entry[0], i = entry[1], j = entry[2], move_time = entry[3];\n            if (i == m - 1 && j == n - 1) return cur_time;\n            int new_move_time = (move_time == 1) ? 2 : 1;\n            int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n            for (int[] dir : dirs) {\n                int ni = i + dir[0], nj = j + dir[1];\n                if (ni < 0 || ni == m || nj < 0 || nj == n) continue;\n                int new_time = Math.max(cur_time, moveTime[ni][nj]) + new_move_time;\n                if (min_time[ni][nj] > new_time) {\n                    min_time[ni][nj] = new_time;\n                    pq.offer(new int[]{new_time, ni, nj, new_move_time});\n                }\n            }\n        }\n        return -1;\n    }\n}\n```\n
['Array', 'Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'C++', 'Java', 'Python3']