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.
Input: [[0,1],[1,0]] → Output: 2Input: [[0,0,0],[1,1,0],[1,1,0]] → Output: 4
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.
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)