Dijkstra's Algorithm
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst, we define row & col accordingly and let\'s initialize our priority queue. We hav
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst, we define row & col accordingly and let\'s initialize our priority queue. We have to cost as its first value in pq because heap will be ordered according to its first value. Then we intialize "cost" 2D array which will keep track of minimum cost to get there. \n\nBFS + Dijstkra \n\nwhile pq is not empty, we will pop each value inside. \nIf we have reached the end, we will return boolean based on its value meets the health or not. \n\nthen we go explore in all directions (up, right, left, down).\n\nif the new coordinates are within the valid boundaries of the grid, we calcualte the new "cost" to reach that cell aka current cost + grid[i][j] \n\nif the new cost to get there is the new minimum and meets lower health count bar, we push that to the queue to go explore more and update cost grid accordingly\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nheap - O(log(k))\nsince we are iterating over 2D mxn array, it will O(mn*log(mn))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(mn) because we are storing in 2D array \n\n# Code\n```python3 []\nclass Solution:\n    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:\n        # find min path cost and compare w health score\n\n        row, col = len(grid), len(grid[0])\n        pq = [(grid[0][0], 0, 0)] # cost, r, c\n        cost = [[float(\'inf\')] * col for _ in range(row)]\n        cost[0][0] = grid[0][0]\n        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n\n        while pq: \n            ct, r, c = heapq.heappop(pq)\n\n            if (r, c) == (row-1, col-1):\n                return ct <= health\n            \n   \n\n            for dx, dy in directions:\n                newX, newY = r + dx, c + dy\n                if 0 <= newX < row and 0 <= newY < col: \n                    newCt = ct + grid[newX][newY]\n                    if newCt < cost[newX][newY] and newCt < health:\n                        heapq.heappush(pq, (newCt, newX, newY))\n                        cost[newX][newY] = newCt\n\n\n        return False\n```
['Heap (Priority Queue)', 'Python3']