1099. Shortest Path with Obstacle Elimination

Given an m x n grid of 0s (empty) and 1s (obstacle) and an integer k, return the minimum number of steps to walk from the top-left cell to the bottom-right cell (moving 4-directionally) if you may remove at most k obstacles along the way, or -1 if impossible. The input is JSON {grid, k}.

Input: JSON {grid, k}.

Output: Integer — minimum steps, or -1.

Examples

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 shortens the path.

Input: {"grid":[[0,1,1],[1,1,1],[1,0,0]],"k":1}
Output: -1
Explanation: Cannot reach with only one removal.

Input: {"grid":[[0]],"k":0}
Output: 0
Explanation: Already at the target.

Constraints

• 1<=rows,cols<=40
• 0<=k<=rows*cols

Asked by