Shortest Path in Binary Matrix

medium graph bfs

Problem

Given an n × n binary matrix, find the length of the shortest path from (0, 0) to (n−1, n−1) where you may move to any of 8 neighbors and only step on 0-cells. Return -1 if unreachable.

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

Output4

Path (0,0) → (0,1) → (0,2) → (1,2) → (2,2). Length counts cells visited.

grid (rows separated by ';' — each row is 0/1)

from collections import deque
def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n-1][n-1]:
        return -1
    dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    q = deque([(0, 0, 1)])
    seen = {(0, 0)}
    while q:
        r, c, d = q.popleft()
        if r == n - 1 and c == n - 1:
            return d
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

function shortestPathBinaryMatrix(grid) {
  const n = grid.length;
  if (grid[0][0] || grid[n-1][n-1]) return -1;
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
  const q = [[0, 0, 1]];
  const seen = new Set(["0,0"]);
  while (q.length) {
    const [r, c, d] = q.shift();
    if (r === n - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      const key = nr + "," + nc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0 && !seen.has(key)) {
        seen.add(key);
        q.push([nr, nc, d + 1]);
      }
    }
  }
  return -1;
}

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
        int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        Deque<int[]> q = new ArrayDeque<>();
        boolean[][] seen = new boolean[n][n];
        q.offer(new int[]{0, 0, 1});
        seen[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1], d = cur[2];
            if (r == n - 1 && c == n - 1) return d;
            for (int[] dd : dirs) {
                int nr = r + dd[0], nc = c + dd[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0 && !seen[nr][nc]) {
                    seen[nr][nc] = true;
                    q.offer(new int[]{nr, nc, d + 1});
                }
            }
        }
        return -1;
    }
}

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    if (grid[0][0] || grid[n-1][n-1]) return -1;
    int dirs[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    queue<tuple<int,int,int>> q;
    q.push({0, 0, 1});
    vector<vector<bool>> seen(n, vector<bool>(n, false));
    seen[0][0] = true;
    while (!q.empty()) {
        auto [r, c, d] = q.front(); q.pop();
        if (r == n - 1 && c == n - 1) return d;
        for (auto& dd : dirs) {
            int nr = r + dd[0], nc = c + dd[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !grid[nr][nc] && !seen[nr][nc]) {
                seen[nr][nc] = true;
                q.push({nr, nc, d + 1});
            }
        }
    }
    return -1;
}

Explanation

We want the shortest path through open cells on a grid, and every move costs the same. That's the textbook case for BFS: it explores cells in order of distance, so the first time it reaches the goal it has found the shortest route. The only twist here is that moves go in 8 directions, including diagonals.

We start at (0,0) with distance 1 (the path length counts cells, not edges) and mark it seen. The queue holds (row, col, dist) triples.

Each time we dequeue a cell, we first check if it's the target (n-1, n-1) — if so, its dist is the answer. Otherwise we look at all 8 neighbors and enqueue any that are in bounds, equal to 0, and not yet seen, each with dist + 1. Marking seen when enqueuing prevents revisiting.

Example: [[0,0,0],[1,1,0],[1,1,0]]. BFS walks across the open top row and down the right column: (0,0) → (0,1) → (0,2) → (1,2) → (2,2), a path of 4 cells.

If the start or end is blocked, or the queue empties without reaching the target, there's no path and we return -1.

Time: O(n²) Space: O(n²)