[Python3] Dijkstra - Detail Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. Initialization:\n\n-
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Initialization:**\n\n- `m` and `n` store the dimensions of the grid.\n- `distance` is a 2D matrix initialized with `float("inf")` to represent the minimum cost to reach each cell.\n- `distance[0][0]` is set to `-health + grid[0][0]`, as the initial health is deducted from the first cell\'s value.\n- `pq` is a priority queue initialized with the starting cell\'s distance, row, and column.\n\n**2. Dijkstra\'s Algorithm:**\n\n- The `while` loop iterates while the priority queue is not empty.\n- `d, i, j` are extracted from the priority queue, representing the minimum distance, row, and column of the current cell.\n- For each neighbor cell (up, down, left, right), the following checks are performed:\n    - If the neighbor cell is out of bounds, skip it.\n    - If the current distance to the neighbor cell (calculated as `d + grid[ci][cj]`) is less than the previously stored distance (`distance[ci][cj]`), update the distance and add the neighbor cell to the priority queue.\n\n**3. Return Value:**\n\n- After the loop finishes, the function returns `distance[m - 1][n - 1] < 0`. This means that if the distance to reach the bottom-right corner is negative, it\'s possible to reach it with the given health. Otherwise, it\'s not possible.\n\nIn essence, the function uses Dijkstra\'s algorithm to find the shortest path from the top-left corner to the bottom-right corner, considering the health gained or lost at each cell. If the final distance is negative, it indicates that the player can reach the destination with the given health.\n\n# Complexity\n- Time complexity: $$O(M * N log(M * N))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(M * N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:\n        m, n = len(grid), len(grid[0])\n        distance = [[float("inf") for _ in range(n)] for _ in range(m)]\n        distance[0][0] = -health + grid[0][0]\n        pq = [(distance[0][0], 0, 0)]\n        while pq:\n            d, i, j = heapq.heappop(pq)\n            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n                ci, cj = i + di, j + dj\n                if ci < 0 or ci == m or cj < 0 or cj == n: continue\n                if d + grid[ci][cj] < distance[ci][cj]:\n                    distance[ci][cj] = d + grid[ci][cj]\n                    heapq.heappush(pq, (d + grid[ci][cj], ci, cj))\n        return distance[m - 1][n - 1] < 0\n```
['Array', 'Breadth-First Search', 'Shortest Path', 'Python3']