Given a grid of open cells and obstacles, return the shortest path from the top-left cell to the bottom-right cell when you may remove up to k obstacles. Pattern focus: BFS shortest path. The state must include both position and remaining obstacle removals.
grid = binary matrix, k = maximum obstacles that can be removed
shortest path length from start to end, or -1
Example 1:
Input:
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]] k = 1
Output:
6
Explanation:
Removing one obstacle makes a short path possible.
Example 2:
Input:
grid = [[0,1,1],[1,1,1],[1,0,0]] k = 1
Output:
-1
Explanation:
One removal is not enough to connect start and target.
Example 3:
Input:
grid = [[0,0],[0,0]] k = 0
Output:
3
Explanation:
An open 2 x 2 grid needs three cells on the path.