Minimum Moves to Reach Bottom-Right in a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either . (an open cell) or # (a blocked cell). The starting position is at the top-left corner (cell (0,0)) and the goal is to reach the bottom-right corner (cell (n-1,m-1)).

You can move in four directions: up, down, left, and right. Your task is to compute the minimum number of moves required to reach the goal. If there is no valid path, output -1.

The moves can be summarized by the following conditions:

• The start cell or the goal cell being blocked (i.e. #) immediately implies there is no valid path.
• If a path exists, output the minimum number of moves needed.

Mathematically, if we denote the grid by \(G\) with indices \(G[i][j]\), then the start is \(G[0][0]\) and the goal is \(G[n-1][m-1]\). The result is the minimum number of steps to transform \((0,0)\) to \((n-1,m-1)\) using the available moves, or \(-1\) if no such sequence exists.

inputFormat

The first line of input contains two integers n and m \( (1 \leq n, m \leq 1000) \), which denote the number of rows and columns in the grid.

The following n lines each contain a string of m characters (each being either . or #) representing the grid.

All input is read from stdin.

outputFormat

Output a single integer --- the minimum number of moves required to reach the bottom-right corner of the grid, or -1 if no such path exists.

All output should be written to stdout.

## sample

1 1
.

0