3286. Find a Safe Walk Through a Grid LeetCode Solution

In this guide, you will get 3286. Find a Safe Walk Through a Grid LeetCode Solution with the best time and space complexity. The solution to Find a Safe Walk Through a Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Find a Safe Walk Through a Grid solution in C++
  4. Find a Safe Walk Through a Grid solution in Java
  5. Find a Safe Walk Through a Grid solution in Python
  6. Additional Resources
3286. Find a Safe Walk Through a Grid LeetCode Solution image

Problem Statement of Find a Safe Walk Through a Grid

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.

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.

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.

See also  1962. Remove Stones to Minimize the Total LeetCode Solution

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.

Complexity Analysis

  • Time Complexity: O(mn \cdot \texttt{health})
  • Space Complexity: O(mn \cdot \texttt{health})

3286. Find a Safe Walk Through a Grid LeetCode Solution in C++

class Solution {
 public:
  bool findSafeWalk(vector<vector<int>>& grid, int health) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = grid.size();
    const int n = grid[0].size();
    const int initialHealth = health - grid[0][0];
    using T = tuple<int, int, int>;  // (i, j, h)
    queue<T> q{{{0, 0, initialHealth}}};
    vector<vector<vector<bool>>> seen(
        m, vector<vector<bool>>(n, vector<bool>(health + 1)));
    seen[0][0][initialHealth] = true;

    while (!q.empty())
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j, h] = q.front();
        q.pop();
        if (i == m - 1 && j == n - 1 && h > 0)
          return true;
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          const int nextHealth = h - grid[x][y];
          if (nextHealth <= 0 || seen[x][y][nextHealth])
            continue;
          q.emplace(x, y, nextHealth);
          seen[x][y][nextHealth] = true;
        }
      }

    return false;
  }
};
/* code provided by PROGIEZ */

3286. Find a Safe Walk Through a Grid LeetCode Solution in Java

class Solution {
  public boolean findSafeWalk(List<List<Integer>> grid, int health) {
    record T(int i, int j, int h) {}
    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = grid.size();
    final int n = grid.get(0).size();
    final int initialHealth = health - grid.get(0).get(0);
    Queue<T> q = new ArrayDeque<>(List.of(new T(0, 0, initialHealth)));
    boolean[][][] seen = new boolean[m][n][health + 1];
    seen[0][0][initialHealth] = true;

    while (!q.isEmpty())
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek().i;
        final int j = q.peek().j;
        final int h = q.poll().h;
        if (i == m - 1 && j == n - 1 && h > 0)
          return true;
        for (int k = 0; k < 4; ++k) {
          final int x = i + dirs[k][0];
          final int y = j + dirs[k][1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          final int nextHealth = h - grid.get(x).get(y);
          if (nextHealth <= 0 || seen[x][y][nextHealth])
            continue;
          q.offer(new T(x, y, nextHealth));
          seen[x][y][nextHealth] = true;
        }
      }

    return false;
  }
}
// code provided by PROGIEZ

3286. Find a Safe Walk Through a Grid LeetCode Solution in Python

class Solution:
  def findSafeWalk(self, grid: list[list[int]], health: int) -> bool:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(grid)
    n = len(grid[0])
    initialHealth = health - grid[0][0]
    q = collections.deque([(0, 0, initialHealth)])
    seen = {(0, 0, initialHealth)}

    while q:
      for _ in range(len(q)):
        i, j, h = q.popleft()
        if i == m - 1 and j == n - 1 and h > 0:
          return True
        for dx, dy in dirs:
          x = i + dx
          y = j + dy
          if x < 0 or x == m or y < 0 or y == n:
            continue
          nextHealth = h - grid[x][y]
          if nextHealth <= 0 or (x, y, nextHealth) in seen:
            continue
          q.append((x, y, nextHealth))
          seen.add((x, y, nextHealth))

    return False
# code by PROGIEZ

Additional Resources

See also  1508. Range Sum of Sorted Subarray Sums LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.