#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

⊣ practice⊣ open on leetcode ↗

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