Minimum Moves to Deliver the Package

You are given a warehouse represented as a grid with n rows and m columns. Each cell in the grid is either . (an empty space) or * (an obstacle). A drone starts at the top-left cell (position (0,0)) and needs to reach the bottom-right cell (position (n-1,m-1)).

The drone can move in four directions: up, down, left, or right. The goal is to determine the minimum number of moves required for the drone to reach its destination. If the starting cell or the destination cell is blocked or if there is no path from the start to the destination, output -1.

The movement follows the standard grid path-finding. Formally, if a path exists, the answer is the length of the shortest path from (0,0) to (n-1,m-1). The moves are counted as follows:

$$\text{moves}(x,y) = \begin{cases} 0, & \text{if } (x,y)=(0,0) \\ \min_{(x',y') \in \text{neighbors}}(\text{moves}(x',y')) + 1, & \text{otherwise} \end{cases}$$

inputFormat

The input is given via standard input (stdin) and has the following format:

n m
row1
row2
... 
rown

Where:

• n and m are integers representing the number of rows and columns of the grid, respectively.
• Each of the next n lines contains a string of length m consisting of the characters . and *.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of moves required for the drone to reach the destination. If it is impossible to reach the destination, output -1.

## sample

5 5
.....
.***.
.....
.***.
.....

8