Leetcode 1091. Shortest Path in Binary Matrix

Let's understand what we're being asked to do. We have an n×n binary grid where 0 represents an open cell and 1 represents a blocked cell. We need to find the shortest path from the top-left corner (0,0) to the bottom-right corner (n-1,n-1).

Let's trace through an example with a 3×3 grid:

[[0,0,0],
 [1,1,0],
 [0,0,0]]

Starting at (0,0), we can move to any of the 8 adjacent cells (up, down, left, right, and 4 diagonals). One valid path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) has length 5 cells.

Important constraint: We can move in 8 directions (not just 4), which means diagonal moves are allowed! This is different from standard grid problems that only allow up/down/left/right.

Edge cases to consider: What if (0,0) or (n-1,n-1) is blocked? (return -1). What if there's no valid path at all? What if n=1 (single cell grid)?

Since we need the shortest path in an unweighted grid (each step has equal cost), we should explore cells level by level - first all cells reachable in 1 step, then all cells reachable in 2 steps, and so on.

This ensures the first time we reach the destination, we've found the shortest path.

By exploring level by level, we guarantee that when we reach (n-1,n-1), no shorter path exists. Any other path would have been discovered earlier.

This is fundamentally different from exploring as deep as possible first (which might find a long path before discovering a shorter one).

Imagine water spreading from (0,0) outward in all 8 directions. After 1 second, water reaches all cells 1 step away. After 2 seconds, water reaches all cells 2 steps away.

The first moment water touches (n-1,n-1) tells us the shortest distance. We need to track which cells we've already visited (to avoid revisiting) and explore neighbors systematically, always processing closer cells before farther ones.

Use BFS (Breadth-First Search) to explore the grid level by level. Start from (0,0) and add it to a queue with distance 1. For each cell, explore all 8 neighboring cells that are open and unvisited. Mark visited cells to avoid revisiting. The first time we reach (n-1,n-1), return the distance. If the queue becomes empty without reaching the destination, return -1.

from collections import deque
def shortest_path(grid):
    """
    Find shortest 8-directional path from (0,0) to (n-1,n-1) in binary grid.
    Returns path length or -1 if no path exists.
    """
    n = len(grid)
    
    # Check if start or end is blocked
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    
    # BFS initialization
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = [[False] * n for _ in range(n)]
    visited[0][0] = True
    
    # 8 directions: up, down, left, right, and 4 diagonals
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    
    # BFS main loop
    while queue:
        row, col, dist = queue.popleft()
        
        # Check if reached destination
        if row == n - 1 and col == n - 1:
            return dist
        
        # Explore all 8 neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check if neighbor is valid and unvisited
            if 0 <= new_row < n and 0 <= new_col < n and not visited[new_row][new_col] and grid[new_row][new_col] == 0:
                visited[new_row][new_col] = True
                queue.append((new_row, new_col, dist + 1))
    
    # No path found
    return -1

• BFS for shortest path in unweighted graphs: When a problem asks for the *shortest* path in a grid or graph where all edges have equal weight (each step costs 1), BFS guarantees the first path found is optimal - unlike DFS which may find longer paths first. BFS explores layer-by-layer, ensuring distance optimality.
• 8-directional movement pattern: Grid problems may require checking all 8 neighbors (horizontal, vertical, and diagonal) rather than just 4. Store direction vectors as `[(−1,−1), (−1,0), (−1,1), (0,−1), (0,1), (1,−1), (1,0), (1,1)]` and iterate through them systematically to avoid missing valid paths.
• In-place visited marking optimization: Instead of maintaining a separate `visited` set (O(n²) space), modify the input grid directly by marking visited cells as 1 (blocked). This reduces space complexity while preventing revisits - only viable when mutating input is acceptable or you can restore it afterward.
• Start/end cell validation: A critical edge case is checking if `grid[0][0] == 1` or `grid[n−1][n−1] == 1` before starting BFS - if either endpoint is blocked, immediately return -1. Many solutions fail by queuing invalid starting positions or running unnecessary BFS iterations.
• Queue initialization with distance tracking: Initialize BFS queue with `(row, col, distance)` tuples starting at `(0, 0, 1)` - the distance represents path length (number of cells) not steps. This eliminates off-by-one errors and makes the final answer directly retrievable when reaching the target.
• Grid traversal pattern generalization: This BFS grid approach extends to any shortest-path problem with obstacles: maze solving, robot navigation, game pathfinding, or network routing where nodes have binary reachability. Recognize the pattern: 2D grid + obstacles + shortest path = BFS with neighbor exploration.