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
visited.add((0,0,0))
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
visited.add((new_row, new_col, new_obs_elim))
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 Queuequeue = new LinkedList<>(); // enqueue the starting cell queue.add(new int[]{0, 0, k}); // 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) { queue.add(new int[]{row, col+1, remainingObstacles}); queue.add(new int[]{row, col-1, remainingObstacles}); queue.add(new int[]{row+1, col, remainingObstacles}); queue.add(new int[]{row-1, col, remainingObstacles}); } } // 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 visited.add((x, y)) # 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. Queueq = 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 // adjacent cell 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 |