1293. Shortest Path in a Grid with Obstacles Elimination

Given a `m * n` grid, where each cell is either `0` (empty) or `1` (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner `(0, 0)` to the lower right corner `(m-1, n-1)` given that you can eliminate at most `k` obstacles. If it is not possible to find such walk return -1.

Example 1:

```Input:
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is `(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2)`.
```

Example 2:

```Input:
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 1
Output: -1
Explanation:
We need to eliminate at least two obstacles to find such a walk.
```

Constraints:

• `grid.length == m`
• `grid[0].length == n`
• `1 <= m, n <= 40`
• `1 <= k <= m*n`
• `grid[i][j] == 0 or 1`
• `grid[0][0] == grid[m-1][n-1] == 0`

1293. Shortest Path in a Grid with Obstacles Elimination
``````struct Solution;

use std::collections::HashSet;
use std::collections::VecDeque;

impl Solution {
fn shortest_path(grid: Vec<Vec<i32>>, k: i32) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut queue: VecDeque<(usize, usize, i32, i32)> = VecDeque::new();
let mut visited: HashSet<(usize, usize, i32)> = HashSet::new();
queue.push_back((0, 0, k, 0));
visited.insert((0, 0, k));
while let Some((i, j, left, step)) = queue.pop_front() {
if i == n - 1 && j == m - 1 {
return step;
}
let nstep = step + 1;
for &(di, dj) in &[(-1, 0), (1, 0), (0, -1), (0, 1)] {
let ni = i as i32 + di;
let nj = j as i32 + dj;
if 0 <= ni && ni < n as i32 && 0 <= nj && nj < m as i32 {
let ni = ni as usize;
let nj = nj as usize;
let nleft = left - grid[ni][nj];
if nleft >= 0 && visited.insert((ni, nj, nleft)) {
queue.push_back((ni, nj, nleft, nstep));
}
}
}
}
-1
}
}

#[test]
fn test() {
let grid = vec_vec_i32![[0, 0, 0], [1, 1, 0], [0, 0, 0], [0, 1, 1], [0, 0, 0]];
let k = 1;
let res = 6;
assert_eq!(Solution::shortest_path(grid, k), res);
let grid = vec_vec_i32![[0, 1, 1], [1, 1, 1], [1, 0, 0]];
let k = 1;
let res = -1;
assert_eq!(Solution::shortest_path(grid, k), res);
}
``````