Description
Given a grid with obstacles, find the shortest path from top-left to bottom-right. You may eliminate at most k obstacles. Return path length or -1.
Examples
Input:
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1Output:
6Explanation:
Remove one obstacle.
Input:
grid = [[1]], k = 1Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]], k = 2Output:
4Explanation:
Eliminating 2 obstacles along the top row gives the shortest path of 4 steps: (0,0) → (0,1) → (0,2) → (0,3).
Constraints
- •
1 ≤ m, n ≤ 40