← 返回 bloomberg 的题目列表Shortest Path in a Grid with Obstacles Elimination
类型：online_judge
Given an m × n binary matrix grid:
0 is an empty cell that can be traversed.
1 is an obstacle.
The start is (0, 0) and the destination is (m - 1, n - 1).
In one step, you may move up, down, left, or right to an adjacent cell. You may eliminate at most k obstacles; entering a cell with value 1 consumes one elimination.
Return the minimum number of steps required to reach the destination. Return -1 if it is impossible.
Example 1:
Input:
grid = [
[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]
]
k = 1
Output: 6
Example 2:
Input:
grid = [
[0,1,1],
[1,1,1],
[1,0,0]
]
k = 1
Output: -1
Constraints:
1 <= m, n <= 40
1 <= m * n <= 1600
0 <= k <= m * n
grid[i][j] is either 0 or 1
grid[0][0] = grid[m-1][n-1] = 0
For standard input/output, the first line contains m n k, followed by m rows of n space-separated 0/1 values. Print the minimum number of steps.
Example
Input
5 3 1
0 0 0
1 1 0
0 0 0
0 1 1
0 0 0
Output
6