#3286

Medium

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

Find a Safe Walk Through a Grid

Determine if you can safely traverse a binary grid from top-left to bottom-right using limited health points.

array breadth first search graph heap priority queue matrix

Problem Statement

Given an m x n binary matrix grid and an integer health, determine if you can reach the bottom-right corner starting from the top-left corner. You may move in four directions: up, down, left, or right, but your health must remain positive at each step.

Cells with value 1 reduce your health by 1 upon entering. Your goal is to find a path from (0, 0) to (m - 1, n - 1) such that you never run out of health. Return true if such a path exists, otherwise return false.

Examples

Example 1

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1

Output: true

The final cell can be reached safely by walking along the gray cells below.

Example 2

Input: grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3

Output: false

A minimum of 4 health points is needed to reach the final cell safely.

Example 3

Input: grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5

Output: true

The final cell can be reached safely by walking along the gray cells below.

Any path that does not go through the cell (1, 1) is unsafe since your health will drop to 0 when reaching the final cell.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 50
2 <= m * n
1 <= health <= m + n
grid[i][j] is either 0 or 1.

Solution Approach

Breadth-First Search with Health Tracking

Use a BFS queue to explore each cell while tracking remaining health. Only enqueue moves that keep health positive. This guarantees the search only follows viable paths.

Use 01 BFS Optimization

Treat cells with 0 cost as higher priority and cells with 1 cost as lower priority, using a deque to push 0-cost cells to the front. This minimizes unnecessary expansions and efficiently finds the safest path.

Avoid Revisiting Inferior States

Keep a matrix to record the maximum remaining health at each cell. Skip any state where the current health is less than the recorded value to prevent redundant exploration and reduce runtime.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) in the worst case, as each cell is visited at most once with the highest health. Space complexity is also O(m n) for the BFS queue and health tracking matrix.

What Interviewers Usually Probe

Candidate immediately considers BFS with health tracking, not plain DFS.
Candidate optimizes with 01 BFS to handle cells with different costs efficiently.
Candidate handles boundary conditions and health depletion correctly during traversal.

Common Pitfalls or Variants

Common pitfalls

Failing to track health properly can lead to incorrect true/false results.
Revisiting cells without comparing remaining health can cause TLE or wrong paths.
Ignoring cells with value 1 as costly can result in paths that falsely appear safe.

Follow-up variants

Change movement to include diagonals and recalculate paths.
Vary the health decrement for different cells instead of 1 per obstacle.
Determine the minimum starting health needed to guarantee a safe walk.

FAQ

What is the main pattern for Find a Safe Walk Through a Grid?

It is graph traversal using BFS with careful tracking of remaining health points.

How do I know when to use 01 BFS in this problem?

Use 01 BFS when cells have cost 0 or 1, pushing 0-cost moves to the front of the deque to optimize exploration.

Can I move diagonally in this problem?

No, only up, down, left, or right moves are allowed according to the problem constraints.

What happens if health reaches zero in the middle of the grid?

You cannot enter a cell that would reduce health to zero or below; such paths are unsafe.

How should I track visited states to avoid redundant work?

Store the maximum remaining health at each cell and skip processing if the current health is less than the recorded value.

terminal

Solution

Solution 1: BFS

We define a 2D array $\textit{dist}$, where $\textit{dist}[i][j]$ represents the minimum health value required to reach position $(i, j)$ from the top-left corner. Initially, we set $\textit{dist}[0][0]$ to $\textit{grid}[0][0]$ and add $(0, 0)$ to the queue $\textit{q}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])
        dist = [[inf] * n for _ in range(m)]
        dist[0][0] = grid[0][0]
        q = deque([(0, 0)])
        dirs = (-1, 0, 1, 0, -1)
        while q:
            x, y = q.popleft()
            for a, b in pairwise(dirs):
                nx, ny = x + a, y + b
                if (
                    0 <= nx < m
                    and 0 <= ny < n
                    and dist[nx][ny] > dist[x][y] + grid[nx][ny]
                ):
                    dist[nx][ny] = dist[x][y] + grid[nx][ny]
                    q.append((nx, ny))
        return dist[-1][-1] < health

Continue Practicing

#2577 minimum time to visit a cell in a grid #2290 minimum obstacle removal to reach corner #3341 find minimum time to reach last room i