Delivery Truck Path

You are given an n \times n grid representing a city map. Each cell is either a road (.) or blocked (#). A delivery truck starts at the top-left corner (0,0) and must reach the bottom-right corner (n-1, n-1).

The truck can move in four directions: up, down, left, or right by one cell at a time. Your task is to compute the minimum number of moves required to reach the destination. If it is impossible to reach the destination, output -1. Note that when n = 1, the answer is 0.

The number of moves can be formally represented as follows:

$$moves = \min\{\text{number of moves from }(0,0)\text{ to }(n-1,n-1)\}$$

inputFormat

The input is read from stdin and is given in the following format:

• The first line contains a single integer n representing the size of the grid.
• The next n lines each contain a string of length n consisting of the characters . and #. Here, . denotes an open cell and # denotes a blocked cell.

outputFormat

Output a single integer to stdout which represents the minimum number of moves required for the delivery truck to travel from the top-left corner to the bottom-right corner. If it is not possible, output -1.

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

8