Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n - 1, n - 1).

A clear path in a binary matrix is a path from the top-left cell to the bottom-right cell such that:

• All visited cells have a value of 0.
• All adjacent cells in the path are 8-directionally connected (i.e., they differ in at most one row and one column).

The length of a clear path is the number of visited cells.

Return -1 if no such path exists.

Examples

Example 1

Input: grid = [[0,1],[1,0]]

Output: 2

Explanation: The shortest clear path is (0,0) → (1,1), which has length 2.

Example 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]

Output: 4

Explanation: The shortest clear path is (0,0) → (0,1) → (0,2) → (1,2) → (2,2), but a shorter one exists: (0,0) → (0,1) → (1,2) → (2,2) with length 4.

Example 3

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]

Output: -1

Explanation: The top-left cell is 1, so no clear path exists.

Constraints

• n == grid.length == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1