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 = [[0]], k = 0Output:
0Explanation:
With a 1x1 grid containing no obstacle, the source equals the destination, so the path length is 0.
Input:
grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]], k = 2Output:
5Explanation:
The shortest path is 5 steps, e.g. by going via the clear bottom row.
Constraints
- •
1 ≤ m, n ≤ 40