Taco: Shortest Path in a Grid

You are given a grid of characters representing a maze. Each cell is either an empty cell represented by . or an obstacle represented by #. Your task is to find the shortest path from the top-left corner (cell (0,0)) to the bottom-right corner (cell (n-1, m-1)).

You can move in four directions: up, down, left, and right. Diagonal moves are not allowed.

If a path exists, output the number of steps in the shortest path. Otherwise, output \( -1 \).

Input Format: The first line of input contains two integers \( n \) and \( m \), representing the number of rows and columns respectively. The next \( n \) lines each contain a string of length \( m \) where a . indicates an empty cell and a # indicates an obstacle.

Output Format: Output a single integer which is the length of the shortest path from the top-left to the bottom-right corner. If no such path exists, output \( -1 \).

inputFormat

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

n m
row1
row2
...
rown

Example:

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

outputFormat

The output should be printed to standard output (stdout). It is a single integer representing the shortest path length from the top-left corner to the bottom-right corner. If no valid path exists, output \( -1 \).

## sample

5 5
.....
.....
.....
.....
.....

9

</p>