Shortest Path in a Grid with Obstacles

You are given an n x n grid representing a map where each cell is either open (denoted by 0) or blocked by an obstacle (denoted by 1). Your task is to determine the length of the shortest path from the top-left corner to the bottom-right corner by moving only in the four cardinal directions (up, down, left, and right). If no such path exists, output -1.

The distance is defined as the number of moves needed to reach the destination. The starting cell is at position \( (0, 0) \) and the target is at \( (n-1, n-1) \). You must consider that moving into a cell marked with a 1 is not allowed.

Note: The grid is provided in the input with \( n \) on the first line followed by \( n \) lines each containing \( n \) space-separated integers.

inputFormat

The first line contains an integer \( n \) representing the size of the grid. The next \( n \) lines each contain \( n \) space-separated integers (either 0 or 1), representing the grid configuration.

For example:

5
0 0 0 0 0
1 0 1 1 1
1 0 0 0 1
1 1 1 0 0
1 1 1 1 0

outputFormat

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

## sample

5
0 0 0 0 0
1 0 1 1 1
1 0 0 0 1
1 1 1 0 0
1 1 1 1 0

8

</p>