# Solution For Shortest Path In A Grid With Obstacles Elimination

Problem Statement:

The problem is to find the shortest path from the starting point to the target point in a 2D grid, where some cells are obstacles. The grid is represented by a matrix of dimensions m x n. The starting point is located at the cell (0,0) and the target point is located at the cell (m-1,n-1). The player can move in four directions – up, down, left, and right – one step at a time.

However, there is an additional constraint that the player can eliminate obstacles. The player can eliminate at most k obstacles along the way. If the number of obstacles eliminated along any path exceeds k, that path is not considered for the solution.

Detailed Solution:

Let us first start by analyzing the problem and building an understanding of what is required. Clearly, the problem states that it is the shortest path problem. Let us first try to solve the problem, assuming that obstacles cannot be eliminated. We can easily solve the problem using Breadth-First Search (BFS). In the 2D grid, each cell has four neighbors – up, down, left, and right. We can use a queue to perform the BFS. Starting from the starting point (0,0), we can add its neighbors to the queue. We can repeat this process until we reach the target point (m-1,n-1).

However, the additional constraint mentioned in the problem requires us to eliminate at most k obstacles along the path. We can modify the BFS approach to solve this problem. In order to do so, we need to keep track of the number of obstacles that have been eliminated along the path to each cell. Further, we need to add one more parameter in our BFS queue that indicates the number of obstacles eliminated along the path from the starting cell to the current cell. We can start with i=0, and increment it each time we visit an obstacle cell. If i goes greater than k, we simply skip that cell, as we are not allowed to eliminate more than k obstacles along the path.

To keep track of the number of obstacles eliminated along the path, we can use a 3D visited array. The visited array would be indexed by the row, column, and the number of obstacles eliminated along the path. If the current cell has been visited before with the same number of obstacles eliminated along the path, we do not need to add it to the queue again. If it has been visited before with a smaller value of i, we can update the visited array with the new value of i.

We can continue this modified BFS approach until we reach the target cell. At the target cell, we would have reached there through different paths with different number of obstacles eliminated along the path. We can choose the path with the shortest distance traveled from the starting point. We can store the minimum distance to each cell in a 2D array min_dist which stores the minimum distance from the starting cell to a cell (i,j).

Code:

Below is the implementation of the solution using BFS in Python.

class Solution(object):
def shortestPath(self, grid, k):
“””
:type grid: List[List[int]] :type k: int
:rtype: int
“””
m, n = len(grid), len(grid[0])
queue = deque()
visited = set()
min_dist = [[float(‘inf’)] * n for _ in range(m)] queue.append((0,0,0,0)) # row, col, dist, obs_elim
min_dist[0][0] = 0

``````    while queue:
row, col, dist, obs_elim = queue.popleft()

# Check if we have reached the target point
if row == m-1 and col == n-1:
return dist

# Add the neighbors to the queue
for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
new_row, new_col = row+dx, col+dy
if 0 <= new_row < m and 0 <= new_col < n:
# Check if the new cell is an obstacle and if we
# have already eliminated k obstacles
new_obs_elim = obs_elim + grid[new_row][new_col]
if new_obs_elim > k:
continue
if (new_row, new_col, new_obs_elim) in visited:
continue
queue.append((new_row, new_col, dist+1, new_obs_elim))

return -1 # If we reach here, we cannot reach the target cell
``````

The time complexity of the above code is O(mnk) and the space complexity is O(mnk). The time complexity depends on the maximum number of elements we can add to the BFS queue, which is mnk. The space complexity is due to the visited and min_dist arrays.

## Step by Step Implementation For Shortest Path In A Grid With Obstacles Elimination

```class Solution {
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;

// create a visited array to keep track of visited cells
boolean[][][] visited = new boolean[m][n][k+1];

// create a queue for BFS

// enqueue the starting cell

// set the distance to starting point as 0
int distance = 0;

// loop until the queue is empty
while (!queue.isEmpty()) {
// get the size of the current level
int size = queue.size();

// loop through all the nodes of the current level
for (int i=0; i= 0) {
}
}

// increment the distance by 1 after finishing the nodes of the current level
distance++;
}

// if we reach here, it means that the destination is not reachable
return -1;
}
}```
```from collections import deque

def shortestPath(grid, k):
# BFS to find the shortest path
# keep track of the steps and the number of obstacles eliminated
# if the number of obstacles eliminated is more than k, then return

m = len(grid)
n = len(grid[0])

# create a visited set to keep track of visited cells
visited = set()

# create a queue for BFS
queue = deque()

# enqueue the starting cell
queue.append((0, 0, 0))

# set the starting distance to 0
distance = 0

# loop through the queue until it is empty
while queue:
# get the size of the queue
size = len(queue)

# loop through the queue
for i in range(size):
# get the cell coordinates and the number of obstacles eliminated
x, y, obstacles = queue.popleft()

# if the coordinates are out of bounds, then continue
if x < 0 or x >= m or y < 0 or y >= n:
continue

# if the coordinates are already visited, then continue
if (x, y) in visited:
continue

# if the cell is an obstacle, then continue
if grid[x][y] == 1:
continue

# mark the cell as visited

# if the destination is reached, then return the distance
if x == m - 1 and y == n - 1:
return distance

# enqueue the neighbors
queue.append((x + 1, y, obstacles))
queue.append((x - 1, y, obstacles))
queue.append((x, y + 1, obstacles))
queue.append((x, y - 1, obstacles))

# increment the distance
distance += 1```
```var shortestPath = function(grid, k) {
let m = grid.length, n = grid[0].length;
let dp = Array(m).fill(null).map(() => Array(n).fill(-1));
dp[0][0] = k;
let queue = [[0, 0, k]];

while (queue.length > 0) {
let [i, j, k] = queue.shift();
for (let [di, dj] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
let [ni, nj] = [i + di, j + dj];
if (ni < 0 || ni >= m || nj < 0 || nj >= n || grid[ni][nj] === 1 || dp[ni][nj] !== -1) continue;
dp[ni][nj] = dp[i][j] - 1;
if (dp[ni][nj] < 0) continue;
queue.push([ni, nj, dp[ni][nj]]);
}
}

return dp[m - 1][n - 1] === -1 ? -1 : m + n - 2;
};```
```There is no specific C++ solution for this problem, but the following pseudocode may be helpful:

1. Create a 2D array to represent the grid, with each element representing one cell.

2. Initialize all cells in the array to infinity, except for the starting cell, which should be set to 0.

3. For each cell in the grid, check all of its neighbors. If the neighbor is not an obstacle, and its distance from the starting cell is greater than the current cell's distance from the starting cell plus 1, update the neighbor's distance accordingly.

4. Repeat step 3 until all cells have been checked.

5. The shortest path through the grid will now be represented by the distances in the 2D array. The distance from the starting cell to the goal cell will be the length of the shortest path.```
```using System;

namespace shortest_path_in_a_grid_with_obstacles_elimination {

// Class to represent a cell in grid
class Cell {
public int row, col;
public int dist;

public Cell(int row, int col, int dist)
{
this.row = row;
this.col = col;
this.dist = dist;
}
}

class shortest_path_in_a_grid_with_obstacles_elimination {

// M x N matrix
private static int M = 10;
private static int N = 10;

// Below arrays details all 4 possible movements
// from a cell
private static int row[] = { -1, 0, 0, 1 };
private static int col[] = { 0, -1, 1, 0 };

// Function to check if it is possible to go to
// position (row, col) from current position.
// The function returns false if (row, col) is not a
// valid position or has value -1 or it is already
// visited
private static bool isValid(int grid[][], bool visited[][],
int row, int col)
{
return (row >= 0) && (row < M) && (col >= 0) && (col < N)
&& (grid[row][col] == 0) && (!visited[row][col]);
}

// Find shortest path in a matrix with given constraints
private static int BFS(int grid[][], int k, int src_row, int src_col,
int dest_row, int dest_col)
{
// Check if source is valid
if (!isValid(grid, new bool[M][N], src_row, src_col)) {
return -1;
}

// Create a queue for BFS and insert source cell
// with distance 0 in it.
Queue q = new Queue();
q.Enqueue(new Cell(src_row, src_col, 0));

// Mark the source cell as visited
bool[][] visited = new bool[M][N];
visited[src_row][src_col] = true;

// Loop while there are cells in queue
while (q.Count != 0) {
// Remove front cell from the queue and process it
Cell curr = q.Dequeue();

// If we have reached the destination cell,
// we are done
if (curr.row == dest_row && curr.col == dest_col) {
return curr.dist;
}

// Otherwise enqueue its adjacent cells
for (int i = 0; i < 4; i++) {
int row = curr.row + row[i];
int col = curr.col + col[i];

// If adjacent cell is valid, has path and
// not visited yet, enqueue it.
if (isValid(grid, visited, row, col)) {
// increment distance by 1 for each valid
visited[row][col] = true;
q.Enqueue(new Cell(row, col, curr.dist + 1));
}
}
}

// Return -1 if destination cannot be reached
return -1;
}

// Driver code
public static void Main(String[] args)
{
int grid[][] = { { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

int k = 3;
int src_row = 0, src_col = 0;
int dest_row = 3, dest_col = 0;

Console.WriteLine(BFS(grid, k, src_row, src_col, dest_row, dest_col));
}
}
}

// This code is contributed by 29AjayKumar```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]