Shortest Path In A Grid With Obstacles Elimination - Leetcode Solution

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.

1