← 返回 bytedance 的题目列表Shortest Path in a Grid with Obstacles Elimination
类型：online_judge
Problem: Shortest Path in a Grid with Obstacle Elimination
You are given an m x n grid:
grid[i][j] = 0 means an empty cell that can be visited.
grid[i][j] = 1 means an obstacle.
You start from the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1).
In one step, you may move one cell up, down, left, or right.
You may eliminate at most k obstacles. Once an obstacle is eliminated, that cell can be passed through.
Return the minimum number of steps required to reach the destination. If it is impossible, return -1.
Input Format
m n k
grid[0][0] grid[0][1] ... grid[0][n-1]
...
grid[m-1][0] ... grid[m-1][n-1]
Output Format
minimum number of steps
Constraints
1 <= m, n <= 40
0 <= k <= m * n
grid[i][j] is either 0 or 1
Assume grid[0][0] = 0 and grid[m-1][n-1] = 0
Example
Input:
5 3 1
0 0 0
1 1 0
0 0 0
0 1 1
0 0 0
Output:
6
Example
Input
5 3 1
0 0 0
1 1 0
0 0 0
0 1 1
0 0 0
Output
6