BFS - Explore nodes with less health deduction first
Intuition\n Describe your first thoughts on how to solve this problem. \nExplore 4 directions from the current cell => BFS.  \nGo through cell of value 1 will d
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nExplore 4 directions from the current cell => BFS.  \nGo through cell of value 1 will deduct health + need to go to right-most cell with health => Prioritize going through cells with no health deduction. \n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDefine `directions` array to indicate directions we can move our cell.  \nWe use a queue to keep track of the moves that haven\'t been visited. The moves at the beginning of the array will deduct no health, while the moves at the end will deduct health. \n\nWe add the first cell and the health after going into this cell in the queue. Then mark this cell as visited with value `-1`.\n\nWhile there are still moves in the queue:\n- Pop the best move cel from the queue\n- Explore all 4 directions from that move cell:\n- If the new cell is out of grid bound => ignore\n- If the new cell is already visited => ignore\n- If the new cell is our targeted right-most cell: If there is still health left => return True. Else => return false\n- In other cases: If the new cell doesn\'t have health deduction, add it to the top of the queue. Else, append it to the end of the queue.\n\nIf we have exhausted all moves => there is no way to get to the right-most cell without depleting all health. \n# Complexity\n- Time complexity: O(N * M) where N = number of rows, M = number of columns.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nSince we need to explore all cells in the grid to calculate. \n- Space complexity: O(N * M) where the queue needs to store cells. \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        rows, cols = len(grid), len(grid[0])\n        # up, down, left, right\n        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n        queue = deque([(health - grid[0][0], 0, 0)]) # current health, row, col\n        grid[0][0] = -1 # mark first grid as visited\n\n        while queue:\n            cur_health, row, col = queue.popleft()\n            for row_dir, col_dir in directions:\n                new_row, new_col = row + row_dir, col + col_dir\n                if new_row < 0 or new_row >= rows:\n                    continue\n                if new_col < 0 or new_col >= cols:\n                    continue\n                # visited\n                if grid[new_row][new_col] == -1:\n                    continue\n                new_health = cur_health - grid[new_row][new_col]\n                if new_row == rows - 1 and new_col == cols - 1:\n                    return True if new_health > 0 else False\n                if new_health == cur_health:\n                    queue.appendleft((new_health, new_row, new_col))\n                elif 0 < new_health < cur_health:\n                    queue.append((new_health, new_row, new_col))\n                grid[new_row][new_col] = -1\n        \n        return False\n```
['Python3']