328. Shortest Path in Binary Matrix

BFS explores cells in order of distance, so the first time it reaches the bottom-right corner gives the shortest path length. Moves go to all 8 neighbours.

BFS layer by layer

If either corner is blocked, return -1. Otherwise BFS from (0,0) with a distance of 1, marking cells visited as you enqueue them. Each cell expands to its 8 neighbours. The moment the target (n-1,n-1) is dequeued, its distance is the answer.

queue = [(0,0,1)]; grid[0][0] = 1
while queue:
    r,c,d = pop
    if target: return d
    for 8 neighbours in bounds and == 0: mark; enqueue (nr,nc,d+1)
return -1

Worked example

[[0,0,0],[1,1,0],[1,1,0]] → shortest clear path length 4.

Complexity

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

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

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0, 1});
        grid[0][0] = 1;
        int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        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) {
                    grid[nr][nc] = 1;
                    q.add(new int[]{nr, nc, d + 1});
                }
            }
        }
        return -1;
    }
}