Shortest Path in a Grid

In this problem, you are given a maze represented as an n x m grid. Each cell in the grid is either walkable (represented by a dot, .) or blocked (represented by a hash, #). Starting from the top‐left corner (cell (0, 0)), your task is to find the minimum number of moves required to reach the bottom‐right corner (cell (n-1, m-1)) using only the four cardinal moves: up, down, left, and right. If either the starting cell or the destination cell is blocked, or if no valid path exists between them, output -1.

The movement cost between adjacent cells is uniformly 1. The answer should satisfy the formula $\text{Answer} = \min_{path}\left\{ \text{number of moves along the path} \right\}$, and if no such path exists, return -1.

Note: The grid is provided as n lines of exactly m characters each. Use Breadth-First Search (BFS) or any other optimal method to solve this problem.

inputFormat

The input is read from standard input (stdin). The first line contains two integers, n and m, which represent the number of rows and columns of the grid respectively. The following n lines each contain a string of m characters, where each character is either . (for an open cell) or # (for a blocked cell).

outputFormat

Output a single integer to standard output (stdout). This integer is the minimum number of moves required to go from the top-left corner to the bottom-right corner. If it is not possible to reach the destination, output -1.## sample

5 6
......
.###..
...#.#
.#....
......

9