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