453. 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 only 0 cells and is connected in all 8 directions (horizontally, vertically, and diagonally). 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

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