Shortest Path in a Maze

You are given a rectangular maze represented by a grid with m rows and n columns. Each cell in the grid is either . (an open cell) or * (a blocked cell). Your task is to determine the length of the shortest path from the upper-left corner (cell (1,1)) to the lower-right corner (cell (m,n)).

You can move up, down, left, or right from an open cell to another open cell. If there is no valid path from the start to the destination, output -1.

The problem can be formulated as follows: Given a grid, find the length of the shortest path using Breadth-First Search (BFS). The distance for a valid path is the number of cells traversed, including both the starting and ending cells. In mathematical notation, if a valid path exists, output its length \(d\); otherwise, output \(-1\).

inputFormat

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

m n
row1
row2
... 
rowm

Here, m and n are the number of rows and columns respectively. Each of the next m lines contains a string of length n consisting of characters '.' (open cell) or '*' (blocked cell).

outputFormat

Output a single integer via standard output (stdout): the length of the shortest path from the top-left cell (1,1) to the bottom-right cell (m,n). If no such path exists, output -1.

3 3
..*
*.*
...

5