Minimum Moves to Reach End of Grid

You are given an N × M grid consisting of characters . (free cell) and # (blocked cell). The player starts at the top-left cell (0,0) and needs to reach the bottom-right cell (N-1, M-1) using the minimum number of moves. In one move, the player can move one cell up, down, left, or right.

If either the starting cell or the destination cell is blocked, or if the destination cannot be reached, output -1.

The minimum number of moves is defined as the shortest path distance from the start to the end using only valid moves.

The problem can be formalized using the following equation based on Breadth-First Search (BFS):

\[ \text{moves} = \min_{\text{all valid paths}}(\text{number of steps}) \]

inputFormat

The first line of input contains two integers N and M separated by a space. The next N lines each contain a string of M characters which represent the grid.

Example: 3 3 ... .#. ...

outputFormat

Output a single integer representing the minimum number of moves required to reach the destination. If the destination is unreachable, output -1.## sample

3 3
...
.#.
...

4