Shortest Path in Binary Matrix — BFS 8-Directional

Problem

Find the shortest clear path (only 0s) from top-left to bottom-right, moving in 8 directions. Return path length or -1.

Approach — BFS with 8 Directions

Standard BFS level order. Distance = number of cells on path. Early return if start or end is blocked.

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

Solutions

Python

from collections import deque
class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n=len(grid)
        if grid[0][0]==1 or grid[n-1][n-1]==1: return -1
        q=deque([(0,0,1)])
        grid[0][0]=1
        dirs=[(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        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:
                    grid[nr][nc]=1; q.append((nr,nc,d+1))
        return -1

C++

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& g){
        int n=g.size();
        if(g[0][0]||g[n-1][n-1]) return -1;
        queue<tuple<int,int,int>> q; q.push({0,0,1}); g[0][0]=1;
        int dirs[]={-1,0,1};
        while(!q.empty()){
            auto[r,c,d]=q.front();q.pop();
            if(r==n-1&&c==n-1) return d;
            for(int dr:-1..1) for(int dc:-1..1){
                int nr=r+dr,nc=c+dc;
                if(nr>=0&&nr<n&&nc>=0&&nc<n&&g[nr][nc]==0){g[nr][nc]=1;q.push({nr,nc,d+1});}
            }
        }
        return -1;
    }
};

Complexity

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