0773MediumArrayBreadth-First SearchGraph TheoryHeap (Priority Queue)MatrixShortest Path

Shielded Crossing of a Scorched Bay Floor

Tracked in this browser only

Trains the technique from

LeetCode 3286Find a Safe Walk Through a Grid

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_safe_walk(grid: list[list[int]], health: int) -> bool:

Java

public boolean findSafeWalk(int[][] grid, int health)

The intended approach

Time O(m n) for a grid of m rows and n columns: each bay enters the queue a bounded number of times.Space O(m n) for the spend table and the queue.

Work out the least shielding any crossing can spend, then compare it with the budget. Entering a bay costs `0` or `1`, so the frontier can be held in a double-ended queue: a clean neighbour is pushed on the front and keeps the same total, a scorched neighbour is pushed on the back one point higher, which keeps the queue ordered by total spend. Seed the start bay with its own cost, relax the four neighbours of each bay taken off the queue, and finally report whether the budget minus the total for the last bay is still at least `1`. All four directions are relaxed, so a crossing that doubles back is considered.

Pythonentry point: find_safe_walk

from collections import deque


def find_safe_walk(grid, health):
    # Time O(m n), space O(m n). Tile costs are only 0 or 1, so a double-ended
    # queue keeps the frontier sorted by shielding spent without a heap.
    rows = len(grid)
    cols = len(grid[0])
    INF = float("inf")
    spent = [[INF] * cols for _ in range(rows)]
    spent[0][0] = grid[0][0]
    frontier = deque([(0, 0)])
    while frontier:
        r, c = frontier.popleft()
        here = spent[r][c]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                cand = here + grid[nr][nc]
                if cand < spent[nr][nc]:
                    spent[nr][nc] = cand
                    if grid[nr][nc]:
                        frontier.append((nr, nc))
                    else:
                        frontier.appendleft((nr, nc))
    return health - spent[rows - 1][cols - 1] >= 1

The obvious version

Keep a table of the cheapest known spend per bay, seeded at the start bay, and sweep the whole grid over and over relaxing every bay against its four neighbours until a full sweep changes nothing. Slower than a single ordered pass but it needs no argument about the order bays are settled in.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_safe_walk(grid, health):
    rows = len(grid)
    cols = len(grid[0])
    INF = 10 ** 9
    spent = [[INF] * cols for _ in range(rows)]
    spent[0][0] = grid[0][0]
    moving = True
    while moving:
        moving = False
        for r in range(rows):
            for c in range(cols):
                if spent[r][c] == INF:
                    continue
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        cand = spent[r][c] + grid[nr][nc]
                        if cand < spent[nr][nc]:
                            spent[nr][nc] = cand
                            moving = True
    return health - spent[rows - 1][cols - 1] >= 1

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in