Shortest Path in a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either empty (denoted by '.') or contains an obstacle/tree (denoted by '#'). Your task is to calculate the minimum number of moves required to reach from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)). You can move one cell at a time in four directions: up, down, left, or right. If there is no valid path, output -1.

The movement rule can be summarized as follows:

[ \text{Allowed moves: } (x,y) \to (x+1,y),\ (x-1,y),\ (x,y+1),\ (x,y-1) ]

A valid move is one that stays within the grid boundaries and moves into a cell that does not contain an obstacle. Use an appropriate graph traversal (BFS) to compute the shortest path.

inputFormat

The input is read from standard input. The first line contains two space-separated integers n and m, the number of rows and columns respectively. The next n lines each contain a string of m characters, where each character is either '.' (an empty cell) or '#' (an obstacle).

outputFormat

Output a single integer to standard output: the minimum number of moves required to reach the bottom-right corner from the top-left corner. If no path exists, output -1.## sample

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

6