0 - 1 BFS with python, Beats 96%
Intuition\n Describe your first thoughts on how to solve this problem. \nUsing deque instead of heapq to save sorting time. The path(pos) with less obstacles me
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUsing deque instead of heapq to save sorting time. The path(pos) with less obstacles meet will automatically be ranked before those that has been through more. \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)$$ -->\n\n- Space complexity:\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        \n        m, n = len(grid), len(grid[0])\n        dp = [[0] * n for _ in range(m)]\n\n        dq = deque([(-health+grid[0][0], 0, 0)])\n        direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n\n        while dq:\n            h, x, y = dq.popleft()\n            if h >= 0:\n                return False\n\n            if dp[x][y] == 0:\n                dp[x][y] = 1\n\n                if x == m - 1 and y == n - 1:\n                    return True\n\n                for dx, dy in direc:\n                    new_x, new_y = x + dx, y + dy\n\n                    if 0 <= new_x < m and 0 <= new_y < n and dp[new_x][new_y] == 0:\n                        if grid[new_x][new_y] == 0:\n                            dq.appendleft((h, new_x, new_y))\n                        else:\n                            dq.append((h + 1, new_x, new_y))\n```
['Python3']