Minimum Moves to Reach Destination

You are given a grid with n rows and m columns. Each cell is either . representing an empty space or # representing an obstacle. A rover starts at the top-left cell (1, 1) and its goal is to reach the bottom-right cell (n, m) using the minimum number of moves. The rover can move up, down, left, or right.

If the starting cell or the destination cell is blocked, or if there is no path between them, output -1. Otherwise, output the minimum number of moves required.

The problem can be formalized as follows:

Given a grid \(G\) of size \(n \times m\) where each cell \(G_{i,j}\) is either \('.'\) or \( '#' \), find the minimum number of moves to travel from \(G_{1,1}\) to \(G_{n,m}\) using only moves in the four cardinal directions. If it is impossible, return \(-1\).

inputFormat

The input is given from stdin in the following format:

n m
row_1
row_2
... 
row_n

Here, n and m are integers representing the number of rows and columns, respectively. Each of the following n lines contains a string of length m representing the grid row, composed only of characters . and #.

outputFormat

Output a single integer to stdout representing the minimum number of moves required for the rover to reach the destination. If it is not possible to reach the destination, output -1.

## sample

3 3
...
.#.
...

4