We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Path in a Grid with Obstacles Elimination

Difficulty: Hard

Problem Description

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.

Key Insights

  • The grid can contain obstacles which must be navigated around or eliminated.
  • A breadth-first search (BFS) approach is suitable for exploring the shortest path in an unweighted grid.
  • Each state in the BFS needs to track the position in the grid, the number of steps taken, and the number of obstacles eliminated so far.
  • A 3D array or a dictionary can be used to track visited states to prevent cycles and redundant work.

Space and Time Complexity

Time Complexity: O(m * n * k)
Space Complexity: O(m * n * k)

Solution

The problem can be solved using a breadth-first search (BFS) approach. We will utilize a queue to explore the grid and keep track of the current position, the number of steps taken, and the number of obstacles eliminated. The BFS will explore all four possible directions from the current cell and will check if moving into the next cell is possible either directly or by eliminating an obstacle (if we have remaining eliminations). We will maintain a visited structure to avoid revisiting the same cell with the same number of eliminations.

Code Solutions

from collections import deque

def shortestPath(grid, k):
    m, n = len(grid), len(grid[0])
    if m == 0 or n == 0:
        return -1
    
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque([(0, 0, 0, 0)])  # (x, y, steps, obstacles eliminated)
    visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
    visited[0][0][0] = True
    
    while queue:
        x, y, steps, obstacles = queue.popleft()
        
        if x == m - 1 and y == n - 1:
            return steps
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < m and 0 <= ny < n:
                if grid[nx][ny] == 0 and not visited[nx][ny][obstacles]:
                    visited[nx][ny][obstacles] = True
                    queue.append((nx, ny, steps + 1, obstacles))
                elif grid[nx][ny] == 1 and obstacles < k and not visited[nx][ny][obstacles + 1]:
                    visited[nx][ny][obstacles + 1] = True
                    queue.append((nx, ny, steps + 1, obstacles + 1))
    
    return -1
← Back to All Questions