672. Shortest Path in a Grid with Obstacles Elimination

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

Input: JSON {grid, k}.

Output: Integer — the 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 gives a 6-step path.

Input: {"grid":[[0,1,1],[1,1,1],[1,0,0]],"k":1}
Output: -1
Explanation: Not reachable with one removal.

Input: {"grid":[[0]],"k":0}
Output: 0
Explanation: Start equals end.

Constraints

• 1<=m,n<=40
• 0<=k<=m*n

Asked by