0354HardArrayBreadth-First SearchMatrix

Debris Field Crossing

Tracked in this browser only

Trains the technique from

LeetCode 1293Shortest Path in a Grid with Obstacles Elimination

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 has to cross a debris field mapped as grid. It starts on the cell in the top-left corner and has to reach the cell in the bottom-right corner. A cell holding 1 is blocked by debris and a cell holding 0 is clear; both corner cells are clear.

One move carries the drone to a cell that shares an edge with the cell it is on. The drone carries k clearance charges: entering a blocked cell spends one charge and turns nothing else, and with no charges left the drone cannot enter a blocked cell at all. Charges are never recovered.

Return the fewest moves the drone needs to reach the far corner, or -1 when the trip is impossible within the charges it carries.

Examples

Example 1

Input: grid = [[0,0,1,0],[0,0,1,1],[1,0,1,0]], k = 1
Output: 5

The drone moves right, then down twice to the cell in row 2 column 1, spends its charge entering the blocked cell in row 2 column 2, and steps right into the corner. That is five moves.

Example 2

Input: grid = [[0,1,0],[1,0,0],[1,1,1],[1,0,0]], k = 3
Output: 5

One route of five moves spends a charge entering row 1 column 0, steps right, spends a second charge entering row 2 column 1, then goes down and right to the corner. It uses two of the three charges.

Example 3

Input: grid = [[0,1,1],[1,1,1],[1,1,0]], k = 1
Output: -1

Every route from one corner to the other passes through three blocked cells, and the drone carries a single charge, so it can never arrive.

Constraints

m == grid.length
n == grid[r].length
1 <= m, n <= 40
1 <= k <= m * n
grid[r][c] is 0 or 1.
grid[0][0] == 0 and grid[m - 1][n - 1] == 0

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 shortest_path(grid: list[list[int]], k: int) -> int:

Java

public int shortestPath(int[][] grid, int k)

The intended approach

Time O(m * n * k)Space O(m * n) for the spend table, plus up to O(m * n * k) queued states

Sweep breadth-first over states that pair a cell with the number of charges already spent, one move-layer at a time. Keep, per cell, the smallest spend any arrival has managed: an arrival that spends at least as much as a recorded one can never do better later, so it is dropped. Because whole layers are processed in turn, the first time the far corner is entered gives the fewest moves; running the queue dry means no route fits the budget.

Pythonentry point: shortest_path

from collections import deque


def shortest_path(grid, k):
    # Breadth-first over states (row, column, debris cleared so far).  A cell is worth
    # entering again only with a smaller clearance count than any earlier arrival, so
    # the best count per cell prunes the queue; because the sweep goes layer by layer,
    # the first arrival at the far corner is a fewest-move arrival.
    # Time O(m * n * k).  Space O(m * n) for the best-count table plus the queue.
    rows = len(grid)
    cols = len(grid[0])
    if rows == 1 and cols == 1:
        return 0
    best = [[k + 1] * cols for _ in range(rows)]
    best[0][0] = 0
    queue = deque()
    queue.append((0, 0, 0))
    moves = 0
    while queue:
        moves += 1
        for _ in range(len(queue)):
            r, c, cleared = queue.popleft()
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    spent = cleared + grid[nr][nc]
                    if spent <= k and spent < best[nr][nc]:
                        if nr == rows - 1 and nc == cols - 1:
                            return moves
                        best[nr][nc] = spent
                        queue.append((nr, nc, spent))
    return -1

The obvious version

Relax a table of the cheapest debris count reachable within a growing number of moves: with one more move allowed, a cell can be entered from any neighbour, paying for its own debris. Report the first move count at which the far corner costs no more than `k`, and give up once the move count passes the number of distinct states.

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_fewest_moves(grid, k):
    rows = len(grid)
    cols = len(grid[0])
    if rows == 1 and cols == 1:
        return 0
    huge = rows * cols + k + 10
    cost = [[huge] * cols for _ in range(rows)]
    cost[0][0] = 0
    ceiling = rows * cols * (k + 1)
    for moves in range(1, ceiling + 1):
        nxt = [row[:] for row in cost]
        for r in range(rows):
            for c in range(cols):
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    pr = r + dr
                    pc = c + dc
                    if 0 <= pr < rows and 0 <= pc < cols:
                        through = cost[pr][pc] + grid[r][c]
                        if through < nxt[r][c]:
                            nxt[r][c] = through
        cost = nxt
        if cost[rows - 1][cols - 1] <= k:
            return moves
    return -1

How this problem was checked

Reference solution executed against 9 test cases — 9 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