mediumGraphsPure DSA~20 min
Shortest Clear Path in a Binary Grid
A drone crosses a binary grid from the top-left to the bottom-right cell, moving in any of 8 directions but only through clear (0) cells. Find the length of the shortest clear path.
Problem
Given an n x n binary grid (0 = clear, 1 = blocked), return the length of the shortest path from the top-left cell (0,0) to the bottom-right cell (n-1,n-1), moving 8-directionally through clear cells only. Path length counts the number of visited cells. Return -1 if no such path exists.
Input
An n x n binary grid.
Output
An integer: the shortest clear-path length in cells, or -1.
Constraints
- 1 <= n <= 100
- grid[i][j] is 0 or 1.
Examples
Example 1
Input
grid = [[0,1],[1,0]]
Output
2
Move diagonally from (0,0) to (1,1): two cells.
Example 2
Input
grid = [[0,0,0],[1,1,0],[1,1,0]]
Output
4
A 4-cell diagonal-and-down path reaches the corner.