easy da
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python []
class Solution(object):
    def findSafeWalk(self, grid, health):
        """
        :type grid: List[List[int]]
        :type health: int
        :rtype: bool
        """
        # grid[x][y] == -1 -> cell already visited

        m = len(grid)
        n = len(grid[0])
        
        if grid[0][0] == 1:
            health -= 1
            
        grid[0][0] = -1
        safe_cells = deque([(0, 0, health)])
        danger_cells = deque()
        
        while health > 0:
            if safe_cells:  # we will always prioritize safe cells
                r, c, health = safe_cells.popleft()
            elif danger_cells:
                r, c, health = danger_cells.popleft()
            else:
                return False
            
            if health > (m-1-r) + (n-1-c):  
                return True
            
            for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                new_r, new_c = r+dr, c+dc
                if new_r < 0 or new_r >= m or new_c < 0 or new_c >= n or grid[new_r][new_c] < 0:
                    continue
                if grid[new_r][new_c] == 0:
                    safe_cells.append((new_r, new_c, health))
                elif health > 1:   
                    danger_cells.append((new_r, new_c, health-1))
                
                grid[new_r][new_c] = -1 # mark cell as visited
        
        return False
```
['Python']