Write a Python function to find the shortest path in a binary matrix.
DavidLee
Posted by DavidLee
Last Updated: August 20, 2024
Python Pathfinding
Finding the Shortest Path in a Binary Matrix using Python
A binary matrix consists of cells containing either 0 (representing free space) or 1 (representing obstacles). The goal is to determine the shortest path from the top-left corner of the matrix (i.e., cell (0,0)) to the bottom-right corner (i.e., cell (n-1, n-1)) while only moving through 0s. Movements can be made in eight possible directions: up, down, left, right, and the four diagonals. To find the shortest path, a common approach is to use the Breadth-First Search (BFS) algorithm. BFS is particularly suitable for unweighted grids because it explores all possible paths in layers, ensuring that the shortest path is found first. Here is a Python function that implements this logic: 
from collections import deque

def shortest_path_binary_matrix(grid):
    if not grid or grid[0][0] == 1 or grid[-1][-1] == 1:
        return -1  # Return -1 if the starting or ending cell is blocked

    n = len(grid)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
    
    # Initialize a queue for BFS
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = set((0, 0))
    
    while queue:
        x, y, distance = queue.popleft()
        
        # If we reach the bottom-right corner, return the distance
        if x == n - 1 and y == n - 1:
            return distance
        
        # Explore all possible directions
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # Check if the next cell is within bounds and not visited
            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0 and (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, distance + 1))
    
    return -1  # Return -1 if there's no path to the bottom-right corner
Explanation of the Function:
1. Initial Checks: The function first checks if the grid is empty or if the starting or ending positions are blocked (cells with 1). If any of these conditions are met, -1 is returned, indicating that a path cannot be found. 2. BFS Initialization: A queue is initialized to facilitate the BFS traversal. Each element in the queue is a tuple containing the current cell's coordinates and the distance from the start (initialized at 1). 3. BFS Execution: The function employs a while loop to explore each cell: - It dequeues a position and checks if it is the target (bottom-right corner). - If the target is reached, the distance is returned. - Otherwise, it explores all possible moves. - Valid moves are those that remain within bounds, land on 0, and have not been visited previously. 4. Termination: If the queue is exhausted without reaching the target, -1 is returned, indicating that no valid path exists.
Example Usage:
matrix = [
    [0, 0, 0],
    [1, 0, 1],
    [0, 0, 0]
]
print(shortest_path_binary_matrix(matrix))  # Output: 4
This implementation is efficient for medium-sized matrices and effectively finds the shortest path if it exists.
Default Image