Find a Safe Walk Through a Grid
MediumProblem Statement
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 reach the lower-right corner (m - 1, n - 1).
You can move up, down, left, or right from any cell to its adjacent cells in 4 directions.
Each cell (r, c) has a value:
grid[r][c] == 1is an unsafe cell, reducing your health by1.grid[r][c] == 0is a safe cell, keeping your health unchanged.
You can walk through a cell only if your health remains strictly positive (health >= 1) after visiting that cell (including both the starting cell (0, 0) and the destination cell (m - 1, n - 1)).
Return true if you can reach (m - 1, n - 1) with health >= 1, or false otherwise.
Examples
grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1trueThe path (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (1,2) → (0,2) → (0,3) → (0,4) → (1,4) → (2,4) contains only cells with value 0. Total health lost = 0. Final health = 1 - 0 = 1 >= 1. Hence, return true.
grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5trueThe path (0,0) → (1,0) → (1,1) → (1,2) → (2,2) encounters 4 unsafe cells: grid[0][0]=1, grid[1][0]=1, grid[1][1]=0, grid[1][2]=1, grid[2][2]=1. Total health lost = 4. Final health = 5 - 4 = 1 >= 1. Hence, return true.
grid = [[1,1,1,1]], health = 4falseThe only possible path visits all 4 cells, each with value 1. Total health lost = 4. Final health = 4 - 4 = 0. Since health must be >= 1, we cannot reach the destination safely. Hence, return false.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j] is either 0 or 11 <= health <= m + n