614. Shortest Path in a Grid with Obstacles Elimination
You receive an m × n grid grid where each cell is 0 (walkable) or 1 (an obstacle), plus an integer k. You start in the top-left cell (0, 0) and want to reach the bottom-right cell (m − 1, n − 1), moving one step at a time up, down, left, or right, never leaving the grid.
Along the way you are allowed to demolish at most k obstacles — stepping onto an obstacle destroys it and consumes one unit of your budget.
Return the minimum number of steps needed to reach the bottom-right corner, or -1 if no route exists even with the demolitions. The start and target cells are always walkable.
Example 1:
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation: Walk right along the top row, then straight down the right column, demolishing the single obstacle at (3, 2) on the way: 6 steps. Without any demolition the shortest detour takes 10 steps.
Example 2:
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: Every route from corner to corner has to cross at least two obstacles, but the budget only allows one — the target cannot be reached.
Constraints:
- 1 ≤ m, n ≤ 40
- 1 ≤ k ≤ m * n
- grid[i][j] is 0 or 1
- grid[0][0] == 0 and grid[m-1][n-1] == 0
Hints:
Plain BFS on cells fails here: reaching a cell sooner is not always better if it cost you more demolitions. Two visits to the same cell can be genuinely different.
Make the demolition budget part of the position. BFS over states (row, col, budget left) — a cell may be revisited as long as you arrive with a budget you have never had there before.
Prune hard: remember the best remaining budget seen per cell and skip dominated arrivals, and notice that if k ≥ m + n − 2 you can bulldoze straight to the answer m + n − 2.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Expected output: 6