Shortest Path in Binary Matrix

Intuition

Because every move costs exactly one more cell, the shortest path by cell count is precisely what breadth-first search finds. We start a BFS from the top-left cell, but only if it is open, since otherwise no path can begin. Each layer of the search holds cells reachable in the same number of steps, so the first time we pop the bottom-right cell we already have its shortest distance. To move between cells we consider all eight surrounding neighbors, skipping any that fall outside the grid or are blocked. Marking a cell as blocked the moment we enqueue it prevents revisiting and keeps the traversal linear in the number of cells.

Algorithm walkthrough

1. 1If either the start (0, 0) or the target (n - 1, n - 1) is blocked, return -1 immediately, because no clear path can exist.
2. 2Initialize a queue with the start cell carrying a distance of 1, and mark the start as visited by flipping it to 1.
3. 3Pop the front cell; if it is the bottom-right cell, return its recorded distance.
4. 4Otherwise examine all eight neighbors, and for each in-bounds open neighbor mark it visited and enqueue it with distance + 1.
5. 5Repeat until the queue empties; if the target was never reached, return -1.

Implementation

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:
            return -1
        directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
                      (0, 1), (1, -1), (1, 0), (1, 1)]
        queue = deque([(0, 0, 1)])
        grid[0][0] = 1
        while queue:
            row, col, dist = queue.popleft()
            if row == n - 1 and col == n - 1:
                return dist
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    queue.append((nr, nc, dist + 1))
        return -1