Minimum Moves in a Grid

You are given a grid with n rows and m columns. Each cell of the grid is either walkable or blocked; walkable cells are denoted by . and blocked cells by #.

Your task is to determine the minimum number of moves required to travel from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)) using only the four cardinal directions (up, down, left, right). If there is no valid path, output -1.

The moves follow the rules of a typical breadth-first search (BFS) on a grid. The problem can be formulated using the following formula:

$$\text{result} = \min_{\text{path}\;\in\;\mathcal{P}}\;\text{length}(\text{path})$$

where \(\mathcal{P}\) is the set of all valid paths from (1,1) to (n,m). If no such path exists, the output is -1.

inputFormat

The input is read from stdin and consists of:

1. A line containing two positive integers n and m, representing the number of rows and columns respectively.
2. n lines, each containing a string of length m. Each character is either . (walkable) or # (blocked).

Note: The grid indices start at 1, meaning the top-left cell is (1,1) and the bottom-right is (n,m).

outputFormat

Output a single integer to stdout which represents the minimum number of moves needed to reach the bottom-right cell from the top-left cell. If no valid path exists, output -1.

## sample

4 4
...#
.#..
...#
#...

6