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
- Problem Statement
- Complexity Analysis
- Find a Safe Walk Through a Grid solution in C++
- Find a Safe Walk Through a Grid solution in Java
- Find a Safe Walk Through a Grid solution in Python
- Additional Resources

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.
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
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.