Shortest Path in a Maze

You are given a maze represented as a 2D grid with M rows and N columns. Each cell in the maze is either accessible (denoted by .) or blocked (denoted by #).

Your task is to compute the shortest number of moves required to go from the top-left cell (position (0,0)) to the bottom-right cell (position (M-1, N-1)). Movement is allowed only in the four cardinal directions (up, down, left, right). If it is impossible to reach the destination, output -1.

The distance is measured as the number of moves, where moving from one cell to an adjacent cell counts as one move. Note that the starting position is counted as a distance of 0.

Formally, if we denote coordinates as \( (x, y) \), you can move to \( (x+1, y) \), \( (x-1, y) \), \( (x, y+1) \), or \( (x, y-1) \) provided the destination cell is within the maze and not blocked.

inputFormat

The first line of input contains two integers M and N, representing the number of rows and columns of the maze, respectively.

The next M lines each contain a string of length N, representing a row of the maze. Each character is either . (accessible cell) or # (blocked cell).

Input is given via stdin.

outputFormat

Output a single integer representing the shortest number of moves required to reach the bottom-right corner from the top-left corner. If no such path exists, output -1.

Output is to be printed to stdout.

## sample

3 3
...
.#.
...

4