Minimum Distance in Grid

You are given a grid that represents a city map. The grid is an (n \times m) matrix where each cell is either passable (denoted by a period .) or blocked (denoted by a hash #). Your task is to determine the minimum number of steps required to travel from the top-left corner (cell (0,0)) to the bottom-right corner (cell (n-1,m-1)). At each step, you are allowed to move one unit up, down, left, or right. If the destination is not reachable, output (-1).

Note:

• The first cell (start) and the last cell (destination) might be blocked. In such cases, no valid path exists.
• Steps are counted as the number of moves needed to reach the destination.

The problem may be formally stated as: Given a matrix (G) where each (G_{i,j}) is either . or #, find the minimum distance (d) such that starting at (G_{0,0}) and moving in one of the 4 adjacent directions at each step, you can reach (G_{n-1,m-1}). If no such (d) exists, return (-1).

inputFormat

The input is given via standard input (stdin) with the following format:

1. The first line contains two integers \(n\) and \(m\) separated by a space, representing the number of rows and columns of the grid.
2. The next \(n\) lines each contain a string of length \(m\) consisting only of the characters . and #, which represent a passable cell or a blocked cell respectively.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of steps required to reach from the top-left corner to the bottom-right corner of the grid. If there is no valid path, output (-1).## sample

7 7
...#...
.#...#.
.#.....
..##...
#.#.##.
.......
#.###..

12