MediumArrayBreadth-First SearchMatrix

Shortest Path in Binary Matrix

1 approach, code in every language

You are given an n x n binary grid. Each cell holds either 0, meaning it is open, or 1, meaning it is blocked.

A clear path runs from the top-left cell (0, 0) to the bottom-right cell (n - 1, n - 1). Every cell visited along the path must be open, and any two consecutive cells on the path must be connected in one of the eight directions (horizontally, vertically, or diagonally).

Return the length of the shortest such clear path, measured as the number of cells it visits. If no clear path exists, return -1.

Example 1

Input: grid = [[0,1],[1,0]]

Output: 2

The path visits (0, 0) and then its diagonal neighbor (1, 1), for a total of 2 cells.

Example 2

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]

Output: -1

The start cell (0, 0) is blocked, so no clear path can even begin.

Constraints

n == grid.length == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

Breadth-First Search over 8 Directions

Run a layer-by-layer BFS from the top-left cell, expanding to all eight open neighbors, and return the distance when the bottom-right cell is first reached.

Loading animation…

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

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

Time

O(n^2)

Space

O(n^2)

Each cell is enqueued at most once and examines 8 neighbors, a constant. The grid itself doubles as the visited marker, so no extra visited structure is needed.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Fewest Tiles Across the Floor is our own problem on the technique behind Shortest Path in Binary Matrix: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free