Astronaut Signal Transmission

In a distant galaxy, a team of astronauts stranded on an alien planet must send a signal back to Earth. However, the planet's atmosphere is filled with storm zones that interfere with signal transmission. The astronauts have landed on a grid represented by N rows and M columns. Each cell in the grid is either clear, denoted by ., or contains a storm zone, denoted by #.

The mission is to find the shortest path from the top-left corner of the grid (cell (0,0)) to the bottom-right corner (cell (N-1, M-1)) such that the path does not pass through any storm zones. The astronauts can move up, down, left, or right but cannot move diagonally.

If a valid path exists, output the minimum number of moves required. If there is no valid path, output -1. Note that if the grid consists of only a single cell, the answer is 0 (no moves are needed).

Formula: For a valid path, if the number of moves is d, then the answer is d. Otherwise, the answer is -1.

inputFormat

The first line of input contains two integers N and M separated by a space, representing the number of rows and columns of the grid.

The following N lines each contain a string of length M consisting only of the characters . and #, representing a row of the grid.

outputFormat

Output a single integer which is the minimum number of moves required to reach the destination. If there is no valid path, output -1.

3 3
...
##.
...

4