Shortest Path in a Grid with Obstacles Elimination

if row == m - 1 and col == n - 1:

Check if the current position is the destination.

Because BFS explores states in order of increasing steps, the first time the destination is dequeued guarantees the shortest path, making immediate return correct and optimal.

seen = {(0, 0, k)}

Initialize the visited set with the starting state to prevent revisiting.

Tracking visited states including remaining eliminations prevents redundant exploration and infinite loops, ensuring BFS efficiency.

if valid(nr, nc):

Check if the neighbor is within grid boundaries.

Boundary validation prevents invalid memory access and ensures only valid cells are processed.

if (nr, nc, remain) not in seen:

Check if the neighbor state with the same remaining eliminations has not been visited.

Avoiding revisiting states with identical resource availability prevents redundant work and infinite loops.

return 0 <= row < m and 0 <= col < n

Return a boolean indicating whether row and col satisfy 0 <= row < m and 0 <= col < n.

The chained inequalities implement the exact boundary condition for valid grid indices, preventing out-of-bounds access and ensuring only valid neighbors are processed.

queue = deque([(0, 0, k, 0)])

Initialize the BFS queue with the starting position, full obstacle eliminations, and zero steps taken.

This tuple represents the initial BFS state, capturing position, remaining eliminations, and path length, which is essential for state-aware traversal.

return steps

Return the number of steps taken to reach the destination.

Returning here terminates the search with the minimal path length found by BFS.

seen.add((nr, nc, remain))

Mark the neighbor state as visited with the current remaining eliminations.

Recording visited states ensures BFS does not revisit the same state, maintaining efficiency and correctness.

queue.append((nr, nc, remain, steps + 1))

Enqueue the neighbor state with unchanged remaining eliminations and incremented steps.

Adding the neighbor to the BFS queue continues the search with updated path length while preserving obstacle elimination count.

elif remain and (nr, nc, remain - 1) not in seen:

Check if the neighbor cell is an obstacle and if eliminations remain.

This condition determines if the algorithm can use an elimination to pass through an obstacle.

seen.add((nr, nc, remain - 1))

Mark the neighbor state as visited with one fewer remaining elimination.

Tracking visited states with updated eliminations prevents revisiting less optimal paths and ensures correctness.

queue.append((nr, nc, remain - 1, steps + 1))

Enqueue the neighbor state with decremented remaining eliminations and incremented steps.

This enqueues a valid path that uses one elimination to pass through an obstacle, enabling exploration of all feasible paths.

row, col, remain, steps = queue.popleft()

Dequeue the next state to process, unpacking position, remaining eliminations, and steps.

Extracting the current BFS state is necessary to explore neighbors and update path length.

if grid[nr][nc] == 0:

Check if the neighbor cell is empty (no obstacle).

Distinguishing empty cells allows the algorithm to proceed without using an elimination.

return -1

Return -1 if BFS completes without reaching the destination.

Returning -1 correctly signals that no valid path exists within the given obstacle elimination constraints.

def valid(row, col):

Define a helper function that determines whether a given (row, col) coordinate lies inside the grid.

Centralizing the bounds check in a helper function keeps the BFS neighbor-exploration code simple and reduces the chance of duplicating or miswriting the boundary logic.

while queue:

Begin BFS loop that continues until the queue is empty.

The while loop drives the BFS traversal, processing states layer by layer to guarantee shortest path discovery.

nr, nc = row + dy, col + dx

Calculate the neighbor's row and column indices.

Computing neighbor coordinates is essential for boundary and obstacle checks.

for dx, dy in directions:

Iterate over all four movement directions to explore neighbors.

Exploring all adjacent cells ensures BFS covers the entire reachable grid space.

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

Define the four possible movement directions (right, down, left, up).

Predefining directions simplifies neighbor exploration and reduces code duplication.

m = len(grid)

Store the number of rows in the grid.

Caching the grid height improves readability and avoids repeated calls to len(grid).

n = len(grid[0])

Store the number of columns in the grid.

Caching the grid width improves readability and avoids repeated calls to len(grid[0]).