1293. Shortest Path in a Grid with Obstacles Elimination

## Question

You are given an `m x n`

integer matrix `grid`

where each cell is either `0`

(empty) or `1`

(obstacle). You can move up, down, left, or right from and to an empty cell in **one step**.

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** *. If it is not possible to find such walk return

`k`

obstacles`-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:**

`m == grid.length`

`n == grid[i].length`

`1 <= m, n <= 40`

`1 <= k <= m * n`

`grid[i][j]`

is either`0`

**or**`1`

.`grid[0][0] == grid[m - 1][n - 1] == 0`

## Algorithm

Similar question to pervious one, leverage BFS in a grid to find a spot. Here the spot is the right bottom corner.

The tricky part is that here you can remove at most obstacle, so you will need keep this info when traversing.

## Implementation

class Solution { public int shortestPath(int[][] grid, int k) { int[][] directions = new int[][] { {0, 1}, {0, -1}, {-1, 0}, {1, 0} }; int m = grid.length; int n = grid[0].length; Queue<int[]> queue = new LinkedList<>(); boolean[][][] visited = new boolean[m][n][k + 1]; queue.offer(new int[] {0, 0, k}); int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] node = queue.poll(); int row = node[0]; int col = node[1]; int left = node[2]; if (row == m - 1 && col == n - 1) { return steps; } for (int[] direction : directions) { int newRow = row + direction[0]; int newCol = col + direction[1]; if (newRow < m && newRow >= 0 && newCol < n && newCol >= 0) { if (grid[newRow][newCol] == 1) { if (left - 1 >= 0 && !visited[newRow][newCol][left-1]) { queue.offer(new int[]{newRow, newCol, left - 1}); visited[newRow][newCol][left-1] = true; } } else if (!visited[newRow][newCol][left]) { queue.offer(new int[]{newRow, newCol, left}); visited[newRow][newCol][left] = true; } } } } steps++; } return -1; } }