#3286
Find a Safe Walk Through a Grid
medium · 32.8% accepted · 228 likes · top 10%
array · breadth-first search · graph theory · heap (priority queue) · matrix · shortest path
Description
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.
Solution