Back to Problems

Shortest Path in Binary Matrix

Medium
BFS

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

  • All the visited cells of the path are 0.
  • All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

BFS guarantees the shortest path in an unweighted graph. Here, each cell is a node with 8-directional edges.

Example 1

Input: grid = [[0,1],[1,0]]
Output: 2
Explanation: The path from (0,0) to (1,1) goes diagonally: (0,0) -> (1,1). Length is 2.

Example 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Explanation: The shortest path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2). Length is 4.

Example 3

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
Explanation: The starting cell (0,0) is blocked, so there is no path.

Constraints

  • •n == grid.length
  • •n == grid[i].length
  • •1 <= n <= 100
  • •grid[i][j] is 0 or 1
Show Hints (4)
Hint 1: If the start or end cell is blocked (value 1), return -1 immediately.
Hint 2: Use BFS starting from (0,0). Each cell has up to 8 neighbors.
Hint 3: Track the path length as you traverse.
Hint 4: The first time you reach (n-1, n-1), that is the shortest path length.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?