Minimum Steps to Exit Grid

You are given an n×n grid consisting of walkable cells denoted by . and blocked cells denoted by #. Your task is to find the minimum number of steps required to move from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,n)). You may only move one cell at a time in one of the four cardinal directions (up, down, left, or right). If there is no valid path from the start to the exit, output -1.

The problem can be formalized as follows:

Given an integer n and an n×n grid, find the length of the shortest path from the starting cell at (1,1) to the destination cell at (n,n), moving only to adjacent walkable cells. Formally, if a valid path exists, let the answer be the minimum number of moves m such that: \[ (1,1) \to \cdots \to (n,n)\] where each move is to one of the adjacent cells, and each cell visited contains a .. If no such path exists output \(-1\).

Note: The top-left and bottom-right cells are always provided as part of the grid and can be either walkable or blocked.

inputFormat

The first line of input contains an integer n (the size of the grid). The next n lines each contain a string of length n consisting only of the characters . and #, representing the grid.

Example:

5
.....
.###.
....#
.###.
.....

outputFormat

Output a single integer: the minimum number of steps required to move from the top-left corner to the bottom-right corner, or -1 if no valid path exists.

Example:

8

## sample

5
.....
.###.
....#
.###.
.....

8