Python | Greedy pattern & Shortest Path (Dijkstra)
see the Successfully Accepted Submission\n\n# Code\npython3 []\nimport heapq\nfrom typing import List\n\nclass Solution:\n    def minimumTime(self, grid: List[L
[see the Successfully Accepted Submission](https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid/submissions/1465412021/?envType=daily-question&envId=2024-11-29)\n\n# Code\n```python3 []\nimport heapq\nfrom typing import List\n\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # Down, Up, Right, Left\n        \n        # If the starting point is blocked, return -1\n        if grid[0][1] > 1 and grid[1][0] > 1:\n            return -1\n        \n        m, n = len(grid), len(grid[0])\n        heap = [(0, 0, 0)]  # (time, row, col)\n        visited = [[False] * n for _ in range(m)]  # To track visited cells\n        \n        while heap:\n            time, row, col = heapq.heappop(heap)\n            \n            # If we reach the bottom-right corner, return the time\n            if row == m - 1 and col == n - 1:\n                return time\n            \n            # Skip if already visited\n            if visited[row][col]:\n                continue\n            visited[row][col] = True\n            \n            # Explore all directions\n            for dr, dc in directions:\n                r, c = row + dr, col + dc\n                \n                # Check bounds and if already visited\n                if 0 <= r < m and 0 <= c < n and not visited[r][c]:\n                    if grid[r][c] <= time + 1:\n                        heapq.heappush(heap, (time + 1, r, c))\n                    else:\n                        diff = grid[r][c] - time\n                        if diff % 2 == 1:\n                            heapq.heappush(heap, (grid[r][c], r, c))\n                        else:\n                            heapq.heappush(heap, (grid[r][c] + 1, r, c))\n        \n        # If no valid path is found, return -1\n        return -1\n\n```\n\n\n## Steps of the Algorithm\n\n1. **Input Check**:\n   - If both adjacent cells to the start point `(0, 0)` are inaccessible, return `-1`.\n\n2. **Initialization**:\n   - Define the directions for movement: Down, Up, Right, and Left.\n   - Initialize a min-heap with the starting point `(time=0, row=0, col=0)`.\n   - Create a `visited` matrix to keep track of already processed cells.\n\n3. **Dijkstra-like Exploration**:\n   - While the heap is not empty:\n     1. Pop the smallest element from the heap (the current cell with the smallest "time cost").\n     2. If this cell is the target (bottom-right corner), return the time.\n     3. Mark the cell as visited and explore its neighbors.\n     4. For each valid neighbor:\n        - If the cell can be reached at the current time or the next step, calculate the time to reach and push it into the heap.\n        - If the cell\'s value enforces waiting, compute the next valid time and push it into the heap, adjusting for parity (even/odd time constraints).\n\n4. **No Path Found**:\n   - If the loop ends without reaching the target, return `-1`.\n\n---\n\n## Algorithm Complexity\n\n### Time Complexity\n- **Heap Operations**: Each cell can be pushed into the heap at most once, and each operation is \\(O(\\log(mn))\\), where \\(m \\times n\\) is the grid size.\n- **Neighbor Exploration**: Each cell checks at most 4 neighbors.\n- **Overall**: \\(O((m \\times n) \\log(m \\times n))\\), where \\(m\\) is the number of rows and \\(n\\) is the number of columns.\n\n### Space Complexity\n- **Heap**: Stores up to \\(O(m \\times n)\\) entries for the grid cells.\n- **Visited Matrix**: Requires \\(O(m \\times n)\\) space.\n- **Overall**: \\(O(m \\times n)\\).\n\n---\n\n## Explanation of Key Details\n\n- **Grid Constraints**: The value of `grid[r][c]` indicates the earliest time the cell can be accessed.\n- **Time Adjustment**: If the current time doesn\u2019t align with the cell\u2019s availability due to even/odd parity, the algorithm calculates the next valid time.\n- **Dijkstra-Like Strategy**: Ensures that paths are explored in increasing order of their cumulative time, guaranteeing the minimum time solution.\n\n\n---\n\n## Algorithm Pattern\n\nThis algorithm follows the **Greedy** pattern with **Shortest Path (Dijkstra)** principles:\n1. A **min-heap** is used to always expand the node with the current minimum "time cost."\n2. Cells are visited in increasing order of their minimum reachable time, ensuring the shortest possible path to any cell.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']