Shortest Path in a Grid

You are given one or more grids. For each grid, determine the length of the shortest path from the top-left corner to the bottom-right corner in an \( n \times n \) grid. The grid cells are either open (denoted by .) or blocked (denoted by #). You may only move up, down, left, or right. If a path does not exist, output -1.

The input consists of multiple grids. Each grid starts with an integer n, followed by n lines representing the grid. A grid size of 0 indicates the end of input.

Note: The length of the path is defined as the number of moves taken from the starting position to reach the destination. For a grid of size 1 where the only cell is open, the answer is 0.

The problem can be modeled using a BFS (Breadth-First Search) algorithm. The equation used in BFS to update the distance can be summarized as:

[ \text{distance}{new} = \text{distance}{current} + 1 ]

Use this approach to compute the shortest path length for each grid.

inputFormat

The input is read from standard input. It consists of multiple test cases. Each test case begins with an integer n (\( n \ge 1 \)), denoting the size of the grid. This is followed by n lines, each containing n characters (. for open cells and # for blocked cells). The input terminates with a line containing the integer 0.

outputFormat

For each test case (grid), output a single integer on a separate line representing the length of the shortest path from the top-left corner to the bottom-right corner. If no path is found, output -1.

## sample

5
....#
##.#.
...#.
.#...
..#..
5
#####
#####
#####
#####
#####
0

8
-1

</p>