Maze Navigation

You are given a 2D grid representing a maze. Each cell in the grid is either '.' (an open space) or '#' (an obstacle). Your task is to determine the minimum number of steps required to travel from the top-left corner (position (0,0)) to the bottom-right corner (position (N-1, M-1)) of the grid. Movement is allowed in four cardinal directions (up, down, left, right). If no valid path exists, output -1.

The input consists of one or more test cases. Each test case starts with a line containing two integers N and M (the number of rows and columns), followed by N lines each containing M characters representing the grid. The test cases end with a line containing "0 0".

The answer for each test case should be computed independently and printed on a separate line.

Recall that the shortest path problem in a grid can be solved using a breadth-first search (BFS) algorithm. Mathematically, if we let \(d(i,j)\) denote the distance from the start to cell \((i,j)\), then the update rule is given by:

\[ d(i,j) = \min_{(i',j')\in \mathcal{N}(i,j)} \{ d(i',j') + 1 \} \] where \(\mathcal{N}(i,j)\) denotes the set of adjacent cells that are open (i.e. contain a dot). If the destination is unreachable, the answer is \(-1\).

inputFormat

The input is provided via standard input (stdin) and consists of multiple test cases. Each test case is formatted as follows:

• The first line contains two integers N and M separated by a space.
• The next N lines each contain a string of M characters (each character is either . or #).

The input terminates with a line containing "0 0" which should not be processed.

outputFormat

For each test case, output a single integer representing the minimum number of steps required to go from the top-left corner to the bottom-right corner. If no such path exists, output -1. Each result should be printed on a new line on standard output (stdout).

## sample

5 5
.....
.#.#.
.#.#.
.#.#.
.....
0 0

8

</p>