Shortest Path in a Binary Matrix

You are given an \(n \times n\) binary matrix \(grid\) where each element is either 0 or 1. A cell with a value of 0 is open, and a cell with a value of 1 is blocked. Your task is to determine the length of the shortest path from the top-left corner (cell (0,0)) to the bottom-right corner (cell (n-1, n-1)). Movement is allowed in 8 directions (horizontally, vertically, and diagonally). Formally, if you are at cell \((i, j)\), you may move to \((i+dx, j+dy)\) where \((dx, dy)\) is one of the eight directions.

If no path exists, output \(-1\).

inputFormat

The input is given via standard input (stdin) and is in the following format:

n
row1
row2
...
rown

Here, \(n\) is an integer representing the number of rows (and columns) in the grid, and each subsequent line contains \(n\) space-separated integers (either 0 or 1) representing a row of the matrix.

outputFormat

Output a single integer on standard output (stdout): the length of the shortest path from (0,0) to (n-1, n-1) if such a path exists. If not, output \(-1\).

## sample

1
0

1

</p>