Minimal Moves in a Grid

You are given an \( n \times n \) grid consisting of characters '.' and '#' where a dot ('.') represents an open cell and a hash ('#') represents a blocked cell. You need to determine the minimum number of moves required to move from the top-left cell \((1,1)\) to the bottom-right cell \((n,n)\) if you can only move down or right. If it is impossible to reach the destination, output \(-1\).

Example:

Input:
3
..#
.#.
...
Output:
4

In the above example, one possible path is:

• (1,1) \(\to\) (2,1)
• (2,1) \(\to\) (3,1)
• (3,1) \(\to\) (3,2)
• (3,2) \(\to\) (3,3)

This is the shortest path with 4 moves.

inputFormat

The first line contains an integer ( n ) (the size of the grid). The next ( n ) lines each contain a string of ( n ) characters (each either '.' or '#') describing the grid.

outputFormat

Output a single integer: the minimum number of moves required to go from the top-left cell to the bottom-right cell, or (-1) if no valid path exists.## sample

3
..#
.#.
...

4