Forest Maze Shortest Path

You are given an m x n grid representing a forest. Each cell in the grid is either open (represented by a '.') or blocked (represented by a '#'). Your task is to compute the shortest path from the top-left corner (cell (1,1)) to the bottom-right corner (cell (m,n)). Movement is only allowed in the four cardinal directions: up, down, left, and right.

The length of the path is defined as the number of cells traversed including the start and the end cells. If no valid path exists, output -1.

Mathematical formulation:

Find the minimum length \(L\) such that there exists a sequence of valid moves starting at \( (0,0) \) and ending at \( (m-1,n-1) \) satisfying:

\[ \min L \text{ such that } \forall (i,j) \in \text{path},\ grid[i][j] == '.' \]

If no such sequence exists, then \( L = -1 \).

inputFormat

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

<m> <n>
<row1>
<row2>
...
<row_m>

Where \( m \) and \( n \) are integers representing the number of rows and columns respectively, and each of the following \( m \) lines contains a string of exactly \( n \) characters (each either '.' or '#').

outputFormat

Output a single integer to standard output which is the length of the shortest path from the top-left to the bottom-right cell. If a path does not exist, output -1.

## sample

4 4
....
#.#.
....
###.

7