BFS with two queues
Intuition\nModified BFS search through 2 queues.\n\nDijkstra\'s needs to sort the candiddate after every step. It needs log(mn) time to find the next step. We d
# Intuition\nModified BFS search through 2 queues.\n\nDijkstra\'s needs to sort the candiddate after every step. It needs log(mn) time to find the next step. We don\'t need to sort the heap every time, we just push the higher weight(current weight + 1) in to a new queue.\n\n# Approach\nUsing BFS to explore all the node costs 0 health. Next, explore all the node costs 1 health. Loop until the health is empty or reach the destination.\n\n# Complexity\n- Time complexity:\nO(mn)\n\n- Space complexity:\nO(mn)\n\n# Code\n```python3 []\nclass Solution:        \n    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:\n        n, m = len(grid), len(grid[0])\n        visited = [[False for _ in range(m)] for _ in range(n)]\n        curQue, nextQue = deque(), deque([(0, 0)])\n        visited[0][0] = True\n        if grid[0][0] == 0:\n            health += 1\n        while nextQue or curQue:\n            while curQue:\n                x, y = curQue.popleft()\n                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n                    newX, newY = x + dx, y + dy\n                    if newX >= 0 and newX < m and newY >= 0 and newY < n and not visited[newY][newX]:\n                        visited[newY][newX] = True\n                        if grid[newY][newX] == 0:\n                            if newY == n - 1 and newX == m - 1:\n                                return True\n                            curQue.append((newX, newY))\n                        else:\n                            if newY == n - 1 and newX == m - 1 and health > 1:\n                                return True\n                            nextQue.append((newX, newY))\n            health -= 1\n            if health > 0:\n                curQue = deque(nextQue)\n            nextQue = deque()\n        return False\n```
['Python3']