Find the length of the shortest clear path in a binary matrix from top-left to bottom-right, using 8-directional movement. Clear cells are 0-valued.
Input: [[0,1],[1,0]] → Output: 2Input: [[0,0,0],[1,1,0],[1,1,0]] → Output: 4
BFS from (0,0) exploring 8 directions. First time bottom-right is reached gives shortest path.
- Check corners are 0. Mark start as visited.
- BFS level-by-level: explore all 8 directions.
- Return length when bottom-right is reached.
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;
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)