Shortest Path in a Grid with Obstacles Elimination

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).

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.

---

When we're given a matrix and are required to find either the shortest path or if a path exists, a Breadth-First Search is almost always better than a Depth-First Search in that a DFS will be taking detours where a BFS will draw a straight, linear path to the destination.

What we will do is push the first cell into the queue and check the neighbors that are in the bounds of the array and are zero, if these two cases are valid then we will push them into the queue and explore their neighbors next.  If we have emptied the queue and didn't get to the destination, then there isn't a path to it.  That's a traditional BFS on a matrix.

The only tweak we need to make to the above, traditional BFS on a matrix is the inclusion of this k value.  We'll need to decrement this value whenever we arrive at an obstacle and end a BFS path if it goes past zero.  Not only that, but we will need to include that variable in the list of cells we've seen so that we may visit the same cell, but not with the same amount of attempts for the given BFS path.

---

Let's begin by caching the length and width of the matrix into two variables m, and n, so that we don't have to keep calculating these values.

We will also need a dictionary to keep track of the cells we have visited.

        m, n = len(grid), len(grid[0])       
        seen = {}

---

Next, we will go ahead and create a helper function that tests for valid cells.

It will take a row and column coordinate and will tell us if the cell is in the bounds of the matrix.

        def in_bounds(row:int, col:int) -> bool:
            if row < 0 or col < 0 or row >= m or col >= n:
                return False
            return True

---

After, we will create our BFS function.  This will take the row and column coordinates of the first cell and the number of tries, k, we have.

        def bfs(row:int, col:int, tries:int) -> int:

 

We'll initialize our queue with those values and mark that combination as seen.

            queue = collections.deque([(row, col, tries)])
            seen[(row, col, tries)] = True

 

Within our function, we will create a list of delta neighbor coordinates for the four surrounding cells of each cell.  We can utilize these values later to calculate all four neighbors of a given cell.

            neighbors = [(1,0), (0,1), (-1,0), (0,-1)]

 

We'll also need a distance counter that we will increment after we process a layer within our BFS.

            distance = 0

 

While we still have cells in the queue, we will continue our BFS, searching for the shortest path to the last cell.

            while queue:

 

At the beginning of each iteration, we will calculate the length of the queue.  This will let us know how big the current layer is so that we can increase the distance after that layer has been searched.

                width = len(queue)

 

For each cell in the queue, we will pop the row and column coordinates and check if they're the last coordinates of the matrix.  If they are, then we will return the distance it took to travel to this cell.

                for _ in range(width):
                    row, col, tries = queue.popleft()
                    if (row, col) == (m-1, n-1):
                        return distance

 

If not, we will continue searching its neighbors.

We can get the next row and column for each neighbor by summing each tuple within the neighbors' array with the current row and column.

                    for neighbor in neighbors:
                        next_row,next_col = row+neighbor[0], col+neighbor[1]

 

Here is the only real change we need to make to this common BFS template.

If our neighbor cell is in bounds, we will need to decrement the number of obstacles we can move by the value that is in the neighbor's cell so that we try to remove it if it is an obstacle.

                        if in_bounds(next_row, next_col):
                            next_try = tries - grid[next_row][next_col]

 

When we're planning our next visit to this neighbor cell, we need to include the number of tries we have.  

                            next_visit = (next_row, next_col, next_try)

 

If we have already visited this neighbor cell with this number of tries, then there is no use continuing further because it will result in the same outcome as every previous visit.  Also, if our next try would result in our number of tries being less than zero, then we wouldn't be able to move the obstacle in the way because we'd be out of tries, so we won't continue further in that case either.

If both of those aren't the case, we will mark the next visit as seen and append it to the queue.

                            if (next_visit) not in seen and next_try >= 0:
                                seen[(next_visit)] = True
                                queue.append((next_visit))

 

Once we have processed a layer of nodes in the queue, we will increment the distance value.

                distance += 1

 

If we broke from the loop without returning the destination then we either didn't have enough tries to get past the obstacles or there wasn't a path to it.

            return -1

---

Now that we have our BFS function built, we just need to make the initial call by passing in the first cell's coordinates and the total number of tries we have to move obstacles.

        return bfs(0,0,k)

---