Show problems as
Classic problem #1293HardArrayBreadth-First SearchMatrix

Shortest Path in a Grid with Obstacles Elimination

Real-world version: Debris Field Crossing
Tracked in this browser only
Read Shortest Path in a Grid with Obstacles Elimination on LeetCode(opens in a new tab)

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

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

Python
def shortest_path(grid: list[list[int]], k: int) -> int:
Java
public int shortestPath(int[][] grid, int k)

More on the same topics