Shortest Path in a Grid with Obstacles

You are given an n x n grid where each cell contains either 0 or 1. A cell with 0 indicates an open space, while 1 indicates an obstacle. Your task is to find the length of the shortest path from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,n)). You may move up, down, left, or right. If the starting cell or the destination is blocked, or if there is no valid path, output -1.

Note: In a grid with only one cell, if that cell is not an obstacle, the answer is 1.

The path length is defined as the number of cells visited along the path including both the starting and ending cells.

The problem can be formalized as follows:

Given a grid G of size n x n, find the minimum number of steps required to travel from cell (1,1) to cell (n,n) by moving in the four cardinal directions, subject to the constraints below.

If no such path exists, output -1.

Mathematically, if we denote the grid as \(G[i][j]\), where \(G[i][j]=0\) indicates a free cell and \(G[i][j]=1\) an obstacle, the task is to determine the value:

[ \min_{\text{path }P} |P| \quad \text{subject to } P \text{ is a valid path from } (0,0) \text{ to } (n-1,n-1) \text{ and for any cell } (i,j) \in P,, G[i][j]=0. ]

inputFormat

The first line contains a single integer n which represents the number of rows (and columns) of the grid.

The next n lines each contain n space-separated integers (each either 0 or 1) representing the grid.

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

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

9