#1293
Shortest Path in a Grid with Obstacles Elimination
candidate master · 1525 · lc hard +32 · verified · 46.1% accepted · 4,829 likes · top 30%
Description
In an m x n grid, cells are either empty (0) or contain an obstacle (1). Starting at (0, 0), you want to reach (m - 1, n - 1) using up/down/left/right moves. You may remove at most k obstacles along your path.
Return the shortest path length, or -1 if the destination is unreachable under these conditions.
Example 1:
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
Example 2:
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: We need to eliminate at least two obstacles to find such a walk.
Code
1
2
3