Show problems as
Classic problem #3286MediumArrayBreadth-First SearchGraph TheoryHeap (Priority Queue)MatrixShortest Path

Find a Safe Walk Through a Grid

Real-world version: Shielded Crossing of a Scorched Bay Floor
Tracked in this browser only
Read Find a Safe Walk Through a Grid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey drone must cross the floor of a burnt-out warehouse, laid out as a rectangular grid of bays. grid[i][j] is 1 when bay (i, j) is still scorched and 0 when it is clean. The drone begins on bay (0, 0) and has to finish on bay (grid.length - 1, grid[0].length - 1).

One move takes the drone to a bay directly above, below, left or right of the one it occupies; it may never leave the grid. Every scorched bay the drone occupies, including the bay it starts on and the bay it finishes on, burns one point off its shielding. Clean bays cost nothing. Scorched bays are passable, only expensive. The drone may revisit bays, though occupying a scorched bay again would cost again.

The drone starts with health points of shielding and the crossing counts as safe only if it reaches the final bay with at least 1 point still left. Return true when a safe crossing exists and false otherwise.

Examples

Example 1

Input
grid = [[0,0,0,0,0],[1,1,1,1,0],[0,0,0,0,0],[0,1,1,1,1],[0,0,0,0,0]], health = 1
Output
true

Running right along row 0, down the last column to row 2, left along row 2 to column 0, down to row 4 and right along row 4 reaches the final bay without ever occupying a scorched bay, so the single shielding point is untouched.

Example 2

Input
grid = [[1,0,0],[0,1,0],[0,0,1]], health = 2
Output
false

Bay `(0, 0)` and bay `(2, 2)` are both scorched and the drone has to occupy both, so every crossing burns at least two points and none can end with a point in hand.

Example 3

Input
grid = [[0,0,0,0],[1,1,1,0],[0,0,0,0]], health = 1
Output
true

Row 1 is scorched apart from its last column, so going right along row 0 to column 3 and then straight down to bay `(2, 3)` keeps the drone on clean bays throughout.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= grid.length <= 50
  • 1 <= grid[i].length <= 50
  • 2 <= m * n
  • 1 <= health <= m + n
  • 1 <= health <= 100
  • 0 <= grid[i][j] <= 1
  • grid[i][j] is either 0 or 1.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_safe_walk(grid: list[list[int]], health: int) -> bool:
Java
public boolean findSafeWalk(int[][] grid, int health)

More on the same topics