Shortest Path in Grid

You are given a grid with n rows and m columns. Each cell in the grid is either empty ('.') or an obstacle ('#'). Your task is to determine the length of the shortest path from the top-left cell (position (0, 0)) to the bottom-right cell (position (n-1, m-1)). You can move in four directions: up, down, left, and right. You cannot move into a cell containing an obstacle.

If there is no valid path between the two corners, output -1. Note that if the starting cell or the ending cell is an obstacle, the output should immediately be -1.

The length of the path is the number of moves made.

Input constraints: The input contains two integers n and m followed by n lines each containing m characters (only '.' and '#' are allowed).

Output: A single integer representing the length of the shortest path or -1 if no path exists.

The problem can be modeled using graph theory and solved using the Breadth-First Search (BFS) algorithm. The problem's formula for a clear shortest path (if unobstructed) is given by:

$$L = (n - 1) + (m - 1)$$

when only right and down moves are needed. However, in the presence of obstacles, a full BFS is required.

inputFormat

The input is read from stdin and is structured as follows:

• The first line contains two integers n and m separated by a space.
• The next n lines each contain a string of length m consisting only of the characters '.' (empty cell) and '#' (obstacle).

For example:

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

outputFormat

The output is a single integer printed to stdout that represents the length of the shortest path from the top-left corner to the bottom-right corner. If no such path exists, output -1.

## sample

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

8