Shortest Grid Path with Obstacle Eliminations

Shortest Grid Path with Obstacle Eliminations

You are given an m x n integer grid grid where each cell is either 0 (empty) or 1 (obstacle). You are also given an integer k representing the maximum number of obstacles you are allowed to eliminate.

You start at the top-left corner (0, 0) and want to reach the bottom-right corner (m - 1, n - 1). In each step, you can move one cell up, down, left, or right, provided the target cell is within the grid boundaries.

Return the minimum number of steps needed to walk from (0, 0) to (m - 1, n - 1). If it is impossible to reach the destination after eliminating at most k obstacles, return -1.

Function Signature

def shortest_path(grid: list[list[int]], k: int) -> int:
    pass

Examples

Example 1:

Input: grid = [
    [0, 0, 0],
    [1, 1, 0],
    [0, 0, 0],
    [0, 1, 1],
    [0, 0, 0]
], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacles takes 10 steps. By eliminating the obstacle at (1, 0) or (3, 1), you can reach the bottom-right corner in 6 steps: (0,0) -> (1,0) [eliminate] -> (2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2).

Example 2:

Input: grid = [
    [0, 1, 1],
    [1, 1, 1],
    [1, 0, 0]
], k = 1
Output: -1
Explanation:
We need to eliminate at least 2 obstacles to reach the bottom-right corner, but k = 1, so it is impossible.

Constraints

• m == len(grid)
• n == len(grid[0])
• 1 <= m, n <= 40
• 1 <= k <= m * n
• grid[i][j] is either 0 or 1.
• grid[0][0] == grid[m - 1][n - 1] == 0

Edge Cases to Consider

• The grid consists of a single cell (1 x 1).
• k is sufficiently large (e.g., k >= (m - 1) + (n - 1)), meaning you can take the direct Manhattan path regardless of obstacles.
• Paths where revisiting a cell is beneficial only because you arrive with more remaining obstacle eliminations.