640. 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 to the bottom-right cell, moving in any of 8 directions through cells with value 0. Return -1 if no such path exists. Path length counts the number of visited cells. The input is JSON {grid}.

Input: JSON {grid}.

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

Examples

Input: {"grid":[[0,0,0],[1,1,0],[1,1,0]]}
Output: 4
Explanation: A path of 4 cells exists.

Input: {"grid":[[0,1],[1,0]]}
Output: 2
Explanation: Diagonal move.

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

Constraints

• 1<=n<=100

Asked by