846. Shortest Path in a Binary Matrix

0

Medium

Given a binary matrix grid of size n x n, find the length of the shortest clear path from the top-left cell to the bottom-right cell. If there is no clear path, return -1.
A clear path in a binary matrix is a path that consists of cells with a value of 0. The path must be 8-directionally connected, meaning that adjacent cells must be different and share an edge or a corner. The length of a clear path is determined by the number of visited cells along the path.

Input Format

The first line of input contains an integer N, which represents the dimension of the grid. The next N lines contain binary arrays of length N, representing the binary matrix.

Output Format

The output is an integer representing the length of the shortest path.

Example

Input

3
0 0 0
1 1 0
1 1 0

Output

4

Constraints

1 <= N <= 100

Loading...

View Submissions

Console