Shortest path with wall removal
Your task
You are given an m x n grid where each cell is 0 (open) or 1 (wall). Starting at the top-left (0,0) and moving 4-directionally to the bottom-right (m-1,n-1), you may remove at most k walls along your path. Return the minimum number of steps to reach the bottom-right, or -1 if it cannot be reached even after removing up to k walls. You cannot leave the grid. If the start cell is a wall it counts against your budget too.
Examples
min_steps_with_removals(grid: list[list[int]], k: int) -> intExample 1
Input
min_steps_with_removals([[0, 1, 0], [0, 1, 0], [0, 0, 0]], 1)Output
4