Shortest Path in a Grid

You are given a grid of size \(n \times m\) consisting of open spaces denoted by . and obstacles denoted by #. Your task is to determine the shortest path from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((n-1, m-1)\)) using only up, down, left, and right moves. If it is impossible to reach the destination, output \(-1\).

The grid is provided in the following format:

• The first line contains two integers \(n\) and \(m\), representing the number of rows and columns respectively.
• The next \(n\) lines each contain a string of length \(m\) consisting only of characters . and #.

Your task is to compute the minimal number of moves required to travel from the start to the destination. Note that moving from one cell to an adjacent one (up, down, left, or right) counts as one move.

inputFormat

The input is given from stdin in the following format:

• The first line contains two space-separated integers \(n\) and \(m\) (\(1 \leq n, m \leq 1000\)).
• The following \(n\) lines each contain a string of length \(m\) composed of the characters . (open space) and # (obstacle).

outputFormat

Output a single integer to stdout representing the minimum number of moves needed to travel from the top-left corner to the bottom-right corner. If there is no valid path, output \(-1\).

## sample

3 3
..#
#.#
#..

4

</p>