Shortest Path in a Grid

You are given a grid of characters where each cell is either . (a free cell) or # (an obstacle). Your task is to compute the length of the shortest path from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (n-1, m-1)). You can move only in four directions: up, down, left, and right.

If either the start or the destination cell is an obstacle, or if there is no valid path between them, output -1. Otherwise, output the minimum number of moves required to reach the destination.

The distance is defined as the number of moves made. Formally, if a valid path exists with a total of d moves, then the output should be given by \(d\); if no such path exists, output \(-1\).

inputFormat

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

n m
row1
row2
...
rown

Here, n and m are integers representing the number of rows and columns of the grid, respectively. Each of the following n lines contains a string of exactly m characters, where each character is either . (a free cell) or # (an obstacle).

outputFormat

Print a single integer to standard output (stdout): the minimum number of moves required to get from the top-left corner to the bottom-right corner. If no valid path exists, print -1.

5 5
.....
.###.
.#.#.
.#.#.
.....

8