Matrix Breadth-First Search (BFS) for Shortest Path

Problem: Find the shortest path length from the top-left to bottom-right of a matrix, avoiding obstacles (1s) and not revisiting cells.

1. Approach

• BFS (Level-Order Traversal):
  • Traverse the matrix layer by layer, ensuring the first encounter with the destination is the shortest path.
  • Use a queue to track cells to visit and a visited set to avoid reprocessing.

2. Algorithm

Steps

1. Initialize:
   • Queue with starting position (0, 0) and mark it as visited.
   • Track path length starting at 0.
2. Process Queue Layer by Layer:
   • For each cell in the current queue layer:
     • Check if destination is reached. If yes, return the current path length.
     • Explore four directions (up, down, left, right).
     • Add valid, unvisited cells to the queue and mark them as visited.
   • Increment path length after processing each layer.

Base Cases

• Out of Bounds: Row/column < 0 or ≥ matrix dimensions.
• Obstacle: Cell value is 1.
• Visited Cell: Already processed.

3. Code Implementation

from collections import deque

def shortest_path_bfs(grid):
    rows = len(grid)
    cols = len(grid[0])
    visited = set()
    queue = deque([(0, 0)])  # Start at top-left
    visited.add((0, 0))
    path_length = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, Down, Left, Right

    while queue:
        for _ in range(len(queue)):  # Process current layer
            row, col = queue.popleft()
            # Check if destination reached
            if row == rows-1 and col == cols-1:
                return path_length
            # Explore all directions
            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc
                if (new_row < 0 or new_col < 0 or
                    new_row >= rows or new_col >= cols or
                    grid[new_row][new_col] == 1 or
                    (new_row, new_col) in visited):
                    continue
                visited.add((new_row, new_col))
                queue.append((new_row, new_col))
        path_length += 1  # Increment after processing layer
    return -1  # No path exists

# Example Usage
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]
print(shortest_path_bfs(grid))  # Output: 7 (Shortest Path)

4. Complexity Analysis