BFS Solution
Intuition\nTo solve this problem, the key insight is to treat the grid as a graph where each cell is a node. The challenge lies in managing the obstacle elimina
# Intuition\nTo solve this problem, the key insight is to treat the grid as a graph where each cell is a node. The challenge lies in managing the obstacle elimination limit (`health`) efficiently. We can use Breadth-First Search (BFS), which explores paths layer by layer to find the shortest path. By extending BFS to track the remaining unsafe eliminations, we can determine the shortest path while accounting for the `health` constraint.\n\n# Approach\n1. **Representation**: Use a queue to perform BFS. Each element in the queue contains the current cell coordinates `(row, col)`, the health remaining (`health-unsafe`), and the current path length.\n2. **Optimization**: Use a `visited` set to track visited states, including the remaining obstacle eliminations, i.e., `(row, col)`.\n3. **Early Termination**: If the shortest path without using `health` eliminations is achievable (i.e., `curr_health >= ROW + COL - 2`), return this value directly.\n4. **Neighbor Exploration**:\n   - Move to adjacent cells if they are within bounds.\n   - If the cell is empty (`grid[new_r][new_c] == 0`), proceed without decrementing `health`.\n   - If the cell contains an obstacle (`grid[new_r][new_c] == 1`), decrement `health` before moving.\n5. **Termination**:\n   - If the bottom-right corner `(m-1, n-1)` is reached, return `True`.\n   - If all possibilities are exhausted without reaching the target, return `False`.\n\n# Complexity\n- **Time complexity**:  $$O(m \\cdot n \\cdot k)$$  \n  - Each cell can be visited up to `health` times (with different obstacle counts).  \n  - Neighbor exploration takes constant time for 4 directions.\n- **Space complexity**:  $$O(m \\cdot n \\cdot k)$$ \n  - The queue can grow up to the size of the grid multiplied by `health`.  \n  - The `visited` set stores states of size proportional to $$`m \\cdot n`$$.\n\n# Code\n```python3 []\nclass Solution:\n    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:\n        ROW, COL = len(grid), len(grid[0])\n        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n\n        # Track visited cells with the remaining health\n        visited = set()\n        curr_health = health\n\n        if grid[0][0]:\n            curr_health -= 1\n\n        if curr_health > (ROW - 1) + (COL - 1):\n            return True\n        \n        queue = deque([(0, 0, curr_health)])  # row, col, curr_health\n\n        while queue:\n            r, c, remaining = queue.popleft()\n\n            # If we reach the bottom-right corner, return True\n            if (r, c) == (ROW-1, COL-1) and remaining > 0:\n                return True\n\n            # Mark as visited with the current remaining count\n            if (r, c, remaining) in visited:\n                continue\n            visited.add((r, c, remaining))\n\n            # Explore neighbors\n            for dx, dy in directions:\n                new_r, new_c = r + dx, c + dy\n\n                if 0 <= new_r < ROW and 0 <= new_c < COL:\n                    if grid[new_r][new_c] == 0:\n                        # Move to an empty cell\n                        queue.appendleft((new_r, new_c, remaining))\n\n                    elif remaining > 0 and grid[new_r][new_c] == 1:\n                        # Move to a cell, reducing health count\n                        queue.append((new_r, new_c, remaining - 1, ))\n\n        # If we exhaust the queue without reaching the target, return False\n        return False\n```
['Python3']