Matrix Shortest Path

You are given an n x n matrix where each cell contains either 0 or 1. A value 0 represents water and 1 represents land. Your task is to determine the length of the shortest path from the top-left corner to the bottom-right corner, moving only in the four cardinal directions (up, down, left, right). The path can only pass through cells with a value of 0. If either the starting or ending cell is 1, or if no such path exists, output -1. The distance is measured as the number of moves from the starting cell to the ending cell. Note that if the matrix consists of a single element which is 0, the answer is 0.

The problem can be formally stated as follows: Find the minimum number of steps required to move from cell (0, 0) to cell (n-1, n-1) using only adjacent moves (up, down, left, right) on cells with value 0. If no valid path exists, return -1.

In mathematical notation, if we define the grid as \(G\) and the shortest distance from \( (0, 0) \) to \( (n-1, n-1) \) as \( d \), then:

[ \text{if } G[0][0] = 1 \text{ or } G[n-1][n-1] = 1, \quad d = -1, ]

[ d = \min_{\text{valid paths}} \left( \text{number of moves} \right), \quad \text{or } -1 \text{ if no path exists.} ]

inputFormat

The first line of input is an integer n, representing the size of the matrix. The following n lines each contain n space-separated integers (either 0 or 1) representing the rows of the matrix.

Example:

3
0 0 1
1 0 0
1 1 0

outputFormat

Output a single integer: the length of the shortest path from the top-left corner to the bottom-right corner. If no such path exists, output -1.

## sample

3
0 1 1
0 1 0
1 0 0

-1