## Description

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

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**`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 = 1Output:6Explanation: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 = 1Output:-1Explanation: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`

## Python Solution

Use breadth-first search to find the shortest path to the bottom-right cell. Track the number of eliminations that has been used.

```
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
if not grid or not grid[0]:
return -1
m, n = len(grid), len(grid[0])
target = (m - 1, n - 1)
queue = collections.deque()
initial_state = (0, 0, k)
queue.append(initial_state)
distance = {}
distance[initial_state] = 0
DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]
while queue:
x, y, k = queue.popleft()
if (x, y) == target:
return distance[(x, y, k)]
for dx, dy in DIRECTIONS:
adj_x = x + dx
adj_y = y + dy
if not (0 <= adj_x < len(grid) and 0 <= adj_y < len(grid[0])):
continue
new_state = (adj_x, adj_y, k - grid[adj_x][adj_y])
if new_state in distance:
continue
if new_state[2] >= 0:
queue.append(new_state)
distance[new_state] = distance[(x, y, k)] + 1
return -1
```

- Time Complexity: O(N).
- Space Complexity: O(N).

March 30, 2021 Tutorial: Web Scraping with Python Using Beautiful Soup Learn how to scrape the web with Python! The internet is an absolutely massivread more , with screen shot and code snipets at

Tutorial: Web Scraping with Python Using Beautiful Soup