Shortest Path in Binary Matrix

Problem

Given an n x n binary grid, return the length of the shortest clear path from the top-left cell to the bottom-right cell, or -1 if no such path exists. A clear path visits only cells with value 0, may move in any of the 8 directions between adjacent cells, and its length is the number of cells visited along the path (start and end included).

Constraints

• 1 ≤ n ≤ 100
• grid[i][j] is 0 or 1

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def shortestPathBinaryMatrix(self, grid):
        from collections import deque
        n = len(grid)
        if grid[0][0] or grid[n-1][n-1]:
            return -1
        q = deque([(0, 0, 1)])
        grid[0][0] = 1
        while q:
            r, c, d = q.popleft()
            if r == n-1 and c == n-1:
                return d
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    nr, nc = r+dr, c+dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        q.append((nr, nc, d + 1))
        return -1

Java

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
        int[][] dirs = {
            {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}
        };
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] seen = new boolean[n][n];
        queue.add(new int[]{0, 0});
        seen[0][0] = true;
        int dist = 1; // the start cell itself counts as 1
        while (!queue.isEmpty()) {
            int layerSize = queue.size();
            // Drain a whole BFS layer before the distance ticks up.
            for (int s = 0; s < layerSize; s++) {
                int[] cur = queue.poll();
                if (cur[0] == n - 1 && cur[1] == n - 1) return dist;
                for (int[] d : dirs) {
                    int r = cur[0] + d[0], c = cur[1] + d[1];
                    if (r >= 0 && c >= 0 && r < n && c < n
                            && !seen[r][c] && grid[r][c] == 0) {
                        seen[r][c] = true;
                        queue.add(new int[]{r, c});
                    }
                }
            }
            dist++;
        }
        return -1;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.