Shortest Path in a Square Grid

You are given a warehouse represented as an \(n \times n\) grid. Each cell in the grid contains one of the following integers:

• 0: an empty cell where you can walk.
• 1: a cell occupied by a shelf, which is traversable (but may represent an obstacle in logistics scenarios).
• -1: a blocked cell which cannot be entered.

Your task is to compute the length of the shortest path from the top-left cell (position (0,0)) to the bottom-right cell (position (n-1, n-1)). You can move up, down, left, or right by one cell each step. If the starting cell or the destination cell is not traversable (i.e. not equal to 0), or if no such path exists, output -1.

Note: The path length is defined as the number of moves required to reach the destination.

inputFormat

The input is read from stdin and has the following format:

n
row1_element1 row1_element2 ... row1_elementn
row2_element1 row2_element2 ... row2_elementn
...
rown_element1 rown_element2 ... rown_elementn

Here, the first line contains a single integer \(n\) denoting the size of the grid. Each of the next \(n\) lines contains \(n\) space-separated integers representing the grid.

outputFormat

Output a single integer to stdout representing the length of the shortest path from the top-left to the bottom-right cell. If there is no valid path, output -1.

4
0 0 0 0
1 -1 -1 0
0 0 0 0
0 1 1 0

6