Shortest Path in Binary Matrix

Find the length of the shortest clear path in an n×n binary matrix using 8-directional moves.

matrix bfs shortest-path grid

Given an `n x n` binary matrix `grid` where `0` represents a clear cell and `1` represents a blocked cell, find the length of the shortest path from the top-left cell `(0, 0)` to the bottom-right cell `(n-1, n-1)`. You may move in all 8 directions (up, down, left, right, and all four diagonals) from a clear cell to another clear cell. You cannot move outside the grid or through blocked cells. The path length is the number of cells visited, including the start and end cells.

If no such path exists, return `-1`.

Implement the function `shortestPathBinaryMatrix(grid) -> int` that takes a list of lists of integers and returns an integer.

Constraints

- `1 <= n <= 50`
- `grid[i][j]` is either `0` or `1`
- The start and end cells are always within bounds.
- The grid is always square.
- Time complexity of the optimal solution is O(n^2).

Example

>>> shortestPathBinaryMatrix([[0,1],[1,0]])
2
>>> shortestPathBinaryMatrix([[0,0,0],[1,1,0],[1,1,0]])
4
>>> shortestPathBinaryMatrix([[1,0],[0,0]])
-1

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use BFS since all moves have equal weight.

Track visited cells to avoid revisiting and infinite loops.

If the start or end cell is blocked, return -1 immediately.

Check all 8 directions using a directions list.

Test Results

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