997. Shortest Path in Binary Matrix

Given an n x n binary matrix, return the length of the shortest clear path from the top-left cell (0,0) to the bottom-right cell (n-1,n-1), moving in any of 8 directions through cells with value 0. Path length is the number of visited cells. Return -1 if no such path exists. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the path length, or -1.

Examples

Input: {"grid":[[0,0,0],[1,1,0],[1,1,0]]}
Output: 4
Explanation: Four-cell diagonal path.

Input: {"grid":[[1,0],[0,0]]}
Output: -1
Explanation: Start blocked.

Input: {"grid":[[0]]}
Output: 1
Explanation: Single clear cell.

Constraints

• 1<=n<=100
• cells are 0 or 1

Asked by