# Find a Safe Walk Through a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-a-safe-walk-through-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/find-a-safe-walk-through-a-grid
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Matrix, Graph
---
## Problem
You are given an `m x n` binary matrix `grid` and an integer `health`.

You start on the upper-left corner `(0, 0)` and would like to get to the lower-right corner `(m - 1, n - 1)`.

You can move up, down, left, or right from one cell to another adjacent cell as long as your health _remains_ **positive**.

Cells `(i, j)` with `grid[i][j] = 1` are considered **unsafe** and reduce your health by 1.

Return `true` if you can reach the final cell with a health value of 1 or more, and `false` otherwise.

**Example 1:**

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

**Output:** true

**Explanation:**

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

![](https://assets.glich.co/dsa/find-a-safe-walk-through-a-grid/image0.png)

**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

**Explanation:**

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

![](https://assets.glich.co/dsa/find-a-safe-walk-through-a-grid/image1.png)

**Example 3:**

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

**Output:** true

**Explanation:**

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

![](https://assets.glich.co/dsa/find-a-safe-walk-through-a-grid/image2.png)

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.

# Approaches
## Brute-Force Backtracking (DFS)
This approach uses a brute-force backtracking algorithm to explore all possible simple paths from the starting cell `(0, 0)` to the destination `(m - 1, n - 1)`. It uses a recursive Depth-First Search (DFS) strategy. To prevent getting stuck in cycles within a single path, a `visited` array is maintained for the current exploration path.
**Time:** O(4^(m*n)) - In the worst case, the algorithm explores a number of paths that is exponential in the number of cells in the grid. This is because at each cell, there are up to 3 new directions to explore (excluding the one we came from). · **Space:** O(m * n) - This is for the recursion stack in the worst case, where the path could snake through every cell, and for the `visited` array.
**Pros:** Conceptually simple and easy to understand for those familiar with recursion.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest grid sizes.; The recursion depth can be very large, potentially causing a stack overflow.
### Explanation
The core idea is to try every possible direction (up, down, left, right) from the current cell. If a move is valid (within grid boundaries, not yet visited in the current path, and leaves health positive), we recursively explore from the new cell. If a recursive call eventually reaches the destination, we've found a solution. If an exploration path hits a dead end (no valid moves) or runs out of health, it backtracks to the previous cell and tries a different direction.

This method is exhaustive and guarantees finding a path if one exists, but its downfall is its performance. The number of possible paths in a grid can be enormous, leading to an exponential number of recursive calls.

```java
class Solution {
    private int m, n;
    private int[][] grid;
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean canReach(int[][] grid, int health) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;

        int initialHealth = health - grid[0][0];
        if (initialHealth <= 0) {
            return false;
        }

        boolean[][] visited = new boolean[m][n];
        return findPath(0, 0, initialHealth, visited);
    }

    private boolean findPath(int r, int c, int currentHealth, boolean[][] visited) {
        if (r == m - 1 && c == n - 1) {
            return true;
        }

        visited[r][c] = true;

        for (int[] dir : dirs) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                int nextHealth = currentHealth - grid[nr][nc];
                if (nextHealth > 0) {
                    if (findPath(nr, nc, nextHealth, visited)) {
                        return true;
                    }
                }
            }
        }

        visited[r][c] = false; // Backtrack
        return false;
    }
}
```
### Algorithm
*   Define a recursive function `findPath(row, col, currentHealth, visited)`.
*   The `visited` array tracks cells in the current path to avoid cycles.
*   **Base Case 1:** If `currentHealth` is not positive, the path is invalid. Return `false`.
*   **Base Case 2:** If the current cell `(row, col)` is the destination, a valid path has been found. Return `true`.
*   Mark the current cell as visited: `visited[row][col] = true`.
*   Iterate through the 4 neighbors `(nr, nc)`:
    *   Check if the neighbor is within bounds and not visited.
    *   Calculate health for the next step: `nextHealth = currentHealth - grid[nr][nc]`.
    *   If `nextHealth` is positive, make a recursive call: `findPath(nr, nc, nextHealth, visited)`.
    *   If the recursive call returns `true`, propagate the result by returning `true`.
*   If no neighbor leads to a solution, backtrack by unmarking the cell: `visited[row][col] = false`.
*   Return `false`.
*   The initial call is made from `(0, 0)` after calculating the health cost of the starting cell.

## Dijkstra's Algorithm
A more efficient approach is to treat this as a shortest path problem on a weighted graph. The grid cells act as vertices, and the cost to traverse to a cell is the health it deducts (0 or 1). Dijkstra's algorithm is ideal for finding the path with the minimum total cost from a single source. We find the minimum health reduction required to reach the destination. If this minimum cost is less than the initial health, a safe path exists.
**Time:** O(m * n * log(m * n)) - With `V = m * n` vertices and `E = O(m * n)` edges, Dijkstra's with a binary heap has this complexity. Each vertex is processed once, and each edge relaxation involves a priority queue operation taking `O(log V)` time. · **Space:** O(m * n) - For the `minCost` array and the priority queue, which can store up to `m * n` elements in the worst case.
**Pros:** A standard, correct, and robust algorithm for single-source shortest path problems.; Guaranteed to find the optimal path in terms of minimum health cost.; Efficient enough to pass the given constraints comfortably.
**Cons:** Slightly less efficient than 0-1 BFS for this specific problem since priority queue operations take logarithmic time, whereas a deque offers constant time operations.
### Explanation
We use Dijkstra's algorithm to find the path from `(0, 0)` to `(m-1, n-1)` that minimizes the total health lost. A 2D array, `minCost`, keeps track of the minimum health reduction to reach any cell. A priority queue is used to always explore the path with the currently lowest accumulated cost.

The algorithm is constrained by the `health` limit. We only explore a path to a neighbor if the new total cost does not exceed the available health. If we successfully reach the destination, it means we have found the cheapest possible path, and since all its intermediate steps were affordable, the path is safe.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public boolean canReach(int[][] grid, int health) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        int[][] minCost = new int[m][n];
        for (int[] row : minCost) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        int initialCost = grid[0][0];
        if (health <= initialCost) {
            return false;
        }
        minCost[0][0] = initialCost;
        pq.offer(new int[]{initialCost, 0, 0}); // {cost, row, col}

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int cost = curr[0];
            int r = curr[1];
            int c = curr[2];

            if (cost > minCost[r][c]) {
                continue;
            }

            if (r == m - 1 && c == n - 1) {
                return true;
            }

            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int newCost = cost + grid[nr][nc];
                    if (newCost < health && newCost < minCost[nr][nc]) {
                        minCost[nr][nc] = newCost;
                        pq.offer(new int[]{newCost, nr, nc});
                    }
                }
            }
        }

        return false;
    }
}
```
### Algorithm
*   Model the grid as a graph where cells are vertices and adjacent cells are connected by edges.
*   The weight of an edge moving into a cell `(r, c)` is `grid[r][c]`.
*   The problem becomes finding the shortest path (minimum health cost) from `(0, 0)` to `(m-1, n-1)`.
*   Initialize a `minCost` array with infinity to store the minimum cost to reach each cell.
*   Use a priority queue to store `(cost, row, col)` tuples, prioritized by the lowest `cost`.
*   Start by adding `(grid[0][0], 0, 0)` to the queue, but only if `health > grid[0][0]`.
*   While the queue is not empty:
    *   Extract the cell `(r, c)` with the minimum cost `c`.
    *   If this cell is the destination, return `true`.
    *   For each neighbor `(nr, nc)`:
        *   Calculate the `newCost = c + grid[nr][nc]`.
        *   If `newCost < health` (path is affordable) and `newCost < minCost[nr][nc]` (path is better), update `minCost[nr][nc]` and add `(newCost, nr, nc)` to the queue.

## 0-1 Breadth-First Search (BFS)
The most efficient solution for this problem is a 0-1 Breadth-First Search (BFS). This is an optimization of Dijkstra's algorithm that applies when all edge weights in the graph are either 0 or 1. In our case, moving to a safe cell (`grid[i][j] = 0`) has a cost of 0, and moving to an unsafe cell (`grid[i][j] = 1`) has a cost of 1. By using a double-ended queue (deque) instead of a priority queue, we can achieve a linear time complexity.
**Time:** O(m * n) - Each cell is enqueued and dequeued at most once. Since all deque operations are O(1), the total time complexity is linear in the number of vertices and edges. · **Space:** O(m * n) - For the `minCost` array and the deque, which can store up to `m * n` cells.
**Pros:** The most efficient solution with a linear time complexity.; Optimal for graphs with only 0/1 edge weights.
**Cons:** The logic can be slightly less intuitive than a standard Dijkstra's implementation if one is not familiar with the 0-1 BFS optimization.
### Explanation
The 0-1 BFS algorithm works by maintaining the core property of Dijkstra's—always processing the node with the minimum distance first—but without the overhead of a priority queue. It uses a deque. When exploring neighbors, if the connecting edge has a weight of 0, the neighbor is added to the front of the deque. If the edge has a weight of 1, it's added to the back.

This ensures that all cells reachable with a certain cost `C` are explored before any cells that require a cost of `C+1`. This makes the algorithm as effective as Dijkstra's but faster, as all deque operations (add/remove from front or back) are O(1).

```java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    public boolean canReach(int[][] grid, int health) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        int[][] minCost = new int[m][n];
        for (int[] row : minCost) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        Deque<int[]> deque = new ArrayDeque<>();

        int initialCost = grid[0][0];
        if (health <= initialCost) {
            return false;
        }
        minCost[0][0] = initialCost;
        deque.offerFirst(new int[]{0, 0}); // {row, col}

        while (!deque.isEmpty()) {
            int[] curr = deque.pollFirst();
            int r = curr[0];
            int c = curr[1];
            int cost = minCost[r][c];

            if (r == m - 1 && c == n - 1) {
                return true;
            }

            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int edgeCost = grid[nr][nc];
                    int newCost = cost + edgeCost;

                    if (newCost < health && newCost < minCost[nr][nc]) {
                        minCost[nr][nc] = newCost;
                        if (edgeCost == 0) {
                            deque.offerFirst(new int[]{nr, nc});
                        } else {
                            deque.offerLast(new int[]{nr, nc});
                        }
                    }
                }
            }
        }

        return false;
    }
}
```
### Algorithm
*   This approach is a specialized version of Dijkstra's for graphs with edge weights of only 0 and 1.
*   Use a `minCost` array as in Dijkstra's.
*   Use a double-ended queue (deque) instead of a priority queue.
*   Start by adding the starting cell `(0, 0)` to the deque.
*   While the deque is not empty:
    *   Pop a cell `(r, c)` from the **front** of the deque.
    *   If it's the destination, return `true`.
    *   For each neighbor `(nr, nc)`:
        *   Calculate `newCost` as before.
        *   If the path is affordable and better, update `minCost`.
        *   If the cost to enter the neighbor (`grid[nr][nc]`) is 0, add the neighbor to the **front** of the deque.
        *   If the cost is 1, add the neighbor to the **back** of the deque.

# Solutions
### Java

```java
class Solution {
public
  boolean findSafeWalk(List<List<Integer>> grid, int health) {
    int m = grid.size();
    int n = grid.get(0).size();
    int[][] dist = new int[m][n];
    for (int[] row : dist) {
      Arrays.fill(row, Integer.MAX_VALUE);
    }
    dist[0][0] = grid.get(0).get(0);
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{0, 0});
    final int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      int[] curr = q.poll();
      int x = curr[0], y = curr[1];
      for (int i = 0; i < 4; i++) {
        int nx = x + dirs[i];
        int ny = y + dirs[i + 1];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
            dist[nx][ny] > dist[x][y] + grid.get(nx).get(ny)) {
          dist[nx][ny] = dist[x][y] + grid.get(nx).get(ny);
          q.offer(new int[]{nx, ny});
        }
      }
    }
    return dist[m - 1][n - 1] < health;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool findSafeWalk(vector<vector<int>> &grid, int health) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    dist[0][0] = grid[0][0];
    queue<pair<int, int>> q;
    q.emplace(0, 0);
    int dirs[5] = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop();
      for (int i = 0; i < 4; ++i) {
        int nx = x + dirs[i];
        int ny = y + dirs[i + 1];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
            dist[nx][ny] > dist[x][y] + grid[nx][ny]) {
          dist[nx][ny] = dist[x][y] + grid[nx][ny];
          q.emplace(nx, ny);
        }
      }
    }
    return dist[m - 1][n - 1] < health;
  }
};

```

### Python

```python
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

```