Shortest Path in Binary Matrix

Share

Given an n x n binary matrix, find the length of the shortest clear path from top-left to bottom-right. A clear path only uses cells with value 0. Move in 8 directions. Return -1 if no path.

Example 1
Input: [[0,1],[1,0]] → Output: 2
Example 2
Input: [[0,0,0],[1,1,0],[1,1,0]] → Output: 4

Solution Approach

BFS from (0,0) if it is 0. Explore all 8 directions. First time we reach (n-1,n-1) is the shortest path.

  • If grid[0][0]==1 or grid[n-1][n-1]==1: return -1.
  • BFS queue starts with (0,0,length=1). Mark visited.
  • Explore 8 neighbors. If (n-1,n-1) reached, return current length+1.
  • Return -1 if queue exhausted.
Java
import java.util.*;

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,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0,1});
        grid[0][0] = 1; // mark visited
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == n-1 && cur[1] == n-1) return cur[2];
            for (int[] d : dirs) {
                int r = cur[0]+d[0], c = cur[1]+d[1];
                if (r>=0 && r<n && c>=0 && c<n && grid[r][c]==0) {
                    grid[r][c] = 1;
                    q.offer(new int[]{r,c,cur[2]+1});
                }
            }
        }
        return -1;
    }
}
  • Time Complexity: O(N^2)
  • Space Complexity: O(N^2)