hardGraphsPure DSA~40 min
Shortest Grid Path Removing At Most K Obstacles
A robot crosses a warehouse grid from the top-left to the bottom-right. Some cells hold obstacles. The robot may clear at most k obstacles. Find the shortest path length.
Problem
Given an m x n grid where each cell is 0 (empty) or 1 (obstacle), and an integer k, return the minimum number of steps to walk from (0,0) to (m-1,n-1), being allowed to eliminate at most k obstacles along the way. Moves are up/down/left/right. Return -1 if no such path exists.
Input
An m x n binary grid and an integer k.
Output
An integer: minimum steps, or -1.
Constraints
- 1 <= m, n <= 40
- 1 <= k <= m * n
- grid[i][j] is 0 or 1; grid[0][0] == grid[m-1][n-1] == 0.
Examples
Example 1
Input
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output
6
Removing one obstacle yields a 6-step path.
Example 2
Input
grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output
-1
Even with one removal there is no route.