Shortest Path in Binary Matrix

Find the shortest clear path from top-left to bottom-right in an n x n binary matrix using 8-directional moves.

bfs grid shortest-path matrix

You are given an n x n binary matrix grid where 0 represents a clear cell and 1 represents a blocked cell. You need to find the length of the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). The path can move in 8 directions: up, down, left, right, and all four diagonals. You can only move through cells that are 0, and you cannot step outside the grid. The starting cell and the destination cell must both be 0; if either is 1, return -1. If no such path exists, return -1.

Implement the function `shortest_path_binary_matrix(grid)` that takes a list of lists of integers (each row is a list of 0s and 1s) and returns an integer: the length of the shortest path (number of cells visited, including start and end) or -1 if no path exists.

Assume the grid is always square (n x n) with n >= 1.

Constraints

1 <= n <= 100
Each cell is 0 or 1.
Time complexity should be O(n^2), which is achievable with BFS.

Example

>>> shortest_path_binary_matrix([[0,1],[1,0]])
2

>>> shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])
4

>>> shortest_path_binary_matrix([[1,0,0],[0,0,0],[0,0,0]])
-1

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use breadth-first search (BFS) because each move has equal weight (1).

Represent each cell as (row, col) and keep a queue. Track distances in a separate 2D array.

There are 8 directions: (dx, dy) for all combinations of -1,0,1 except (0,0).

Stop as soon as you reach the bottom-right cell; the first time you reach it is the shortest distance.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.