Minimum Moves to Connect Grid

You are given an n × n grid where each cell contains either a 0 or a 1. A 0 indicates an empty cell and a 1 indicates an obstacle. You must determine the minimum number of moves required to travel from the top-left cell (i.e. cell at position (0,0)) to the bottom-right cell (i.e. cell at position (n-1, n-1)). You may move only in four directions: up, down, left, or right (no diagonal moves are allowed). If there is no valid path, output -1.

The number of moves is defined as the number of steps taken from the starting cell to reach the destination. Mathematically, if you take m moves then the answer is given by \(m\).

Note: The starting and ending cells must be accessible (i.e. they both must contain 0) for a valid path to exist.

inputFormat

The input is read from stdin and is structured as follows:

• The first line contains an integer n, representing the size of the grid.
• The following n lines each contain n space-separated integers (each either 0 or 1) which represent the grid.

outputFormat

Output a single integer to stdout: the minimum number of moves required to travel from the top-left cell to the bottom-right cell. If no valid path exists, output -1.

## sample

1
0

0

</p>