Shortest Path in Binary Matrix

1. Define the problem

Given an n x n binary grid, find the length of the shortest clear path from the top-left cell to the bottom-right cell, moving in any of the eight directions (including diagonals). A cell is clear if its value is 0; return -1 if no such path exists. Run breadth-first search from a single source over the grid, counting cells visited so far — the first time the queue reaches the target cell, that count is the shortest path length.

Constraints

n == grid.length
n == grid_i.length
1 ≤ n ≤ 100
grid_i[j] is 0 or 1

Example

Inputgrid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]

Output4

Explanation The path (0,0) -> (0,1) -> (1,2) -> (2,2) uses 4 cells and is the shortest one available.

2. Know the words first

In plain terms

Source: The one cell the search starts from — here, the top-left corner.

3. Visualize the solution

One cell per open cell of the grid — each shows the path length when BFS reaches it

(0,0)1

(0,1)—

(0,2)—

(1,2)—

(2,2)—

Statusstep 1

Start the queue with (0,0), path length 1. Every other slot is still —.

What happens in this step

grid = [[0,0,0],[1,1,0],[1,1,0]]
queue = [(0,0, len1)]   visited = {(0,0)}

Neither the start nor the target (2,2) is blocked, so BFS proceeds.

Step 1 of 4

Steps to visualize

The row has one slot for each of the five open (value 0) cells in grid = [[0,0,0],[1,1,0],[1,1,0]], read left to right then down. Blocked cells can never be stepped on, so they get no slot.
A slot shows — until the search reaches that cell; then it shows how many cells the path has used so far.
If the start or target cell is blocked, there is no path — return -1 immediately.
Start a queue with the top-left cell, path length 1.
Dequeue a cell and check all eight neighbors; if the target is among them, return the current length + 1.
Otherwise enqueue every unvisited, unblocked neighbor at length + 1.
Repeat until the target is found, or the queue empties (no path exists).

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per open cell of the grid — each shows the path length when BFS reaches it

(0,0)1

(0,1)—

(0,2)—

(1,2)—

(2,2)—

Statusstep 1

Start the queue with (0,0), path length 1. Every other slot is still —.

What happens in this step

grid = [[0,0,0],[1,1,0],[1,1,0]]
queue = [(0,0, len1)]   visited = {(0,0)}

Neither the start nor the target (2,2) is blocked, so BFS proceeds.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function shortestPathBinaryMatrix(grid) {
  const n = grid.length;
  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;
  if (n === 1) return 1;

  const dirs = [
    [1, 0], [-1, 0], [0, 1], [0, -1],
    [1, 1], [1, -1], [-1, 1], [-1, -1],
  ];
  const visited = grid.map((row) => row.map(() => false));
  const queue = [[0, 0, 1]];
  visited[0][0] = true;

  while (queue.length > 0) {
    const [r, c, dist] = queue.shift();
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] === 0) {
        if (nr === n - 1 && nc === n - 1) return dist + 1;
        visited[nr][nc] = true;
        queue.push([nr, nc, dist + 1]);
      }
    }
  }

  return -1;
}

Time: O(n^2)
Space: O(n^2)

6. Test cases

Test cases

Input	Expected	Covers
`grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]`	`4`	example from the docstring
`grid = [[1, 0], [0, 0]]`	`-1`	the starting cell itself is blocked
`grid = [[0]]`	`1`	smallest valid input, a single open cell that is both start and target
`grid = [[1]]`	`-1`	smallest input, but the only cell is blocked
`grid = [[0, 0], [0, 0]]`	`2`	a direct diagonal move is shorter than going around
`grid = [[0, 1, 0], [1, 1, 1], [0, 1, 0]]`	`-1`	the start cell has no open neighbors at all
`grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]`	`4`	a fully open grid where the diagonal path is shortest

Shortest Path in Binary Matrix