Shortest Path in a Grid

You are given a grid of size \(N \times M\) consisting of characters . (which represents an empty cell) and # (which represents an obstacle). Your task is to find the length of the shortest path from the top-left corner (cell (1, 1)) to the bottom-right corner (cell (N, M)). You can move in four directions: left, right, up, and down, but you cannot walk into or through an obstacle.

If there is no valid path, output \(-1\).

Note: The grid indices in the problem are 1-indexed conceptually. In most implementations, you will work with 0-indexed arrays.

The problem can be solved using the Breadth-First Search (BFS) algorithm.

inputFormat

The input is given via stdin and follows this format:

N M
row1
row2
...
rowN

Where:

• N and M (\(1 \leq N, M \leq 1000\)) represent the number of rows and columns respectively.
• Each of the next \(N\) lines contains a string of length \(M\) composed of the characters . and #.

outputFormat

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

## sample

3 3
...
.#.
...

4

</p>