Shortest Obstacle-Aware Path in Grid
Problem Description
You are given a binary matrix `grid` of size `m × n` where `0` represents a passable cell and `1` represents an obstacle. You may also **eliminate at most `k` obstacles** during your traversal.
Return the **minimum number of steps** to travel from the top-left cell `(0, 0)` to the bottom-right cell `(m-1, n-1)`. Each step moves you to an adjacent cell (up, down, left, right). If it is impossible to reach the destination under these constraints, return `-1`.
**Example 1:**
```
Input: grid = [
[0, 1, 0, 0],
[0, 1, 0, 1],
[0, 0, 0, 1],
[1, 1, 0, 0]
], k = 1
Output: 6
```
**Example 2:**
```
Input: grid = [
[0, 1, 1],
[1, 1, 0],
[1, 0, 0]
], k = 0
Output: -1
```
Constraints
- 1 <= m, n <= 40
- 0 <= k <= m * n
- grid[i][j] is either 0 or 1.
- grid[0][0] == 0 and grid[m-1][n-1] == 0.
Follow-up
Extend the problem so that each obstacle has a removal cost, and you have a total budget. Find the minimum steps to reach the destination without exceeding the budget.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.