Minimum Steps to Traverse a Grid

You are given an N x M grid where each cell is either passable (.) or an obstacle (#). Your task is to compute the minimum number of steps required to travel from the top-left cell (1, 1) to the bottom-right cell (N, M) by moving only in the four cardinal directions (up, down, left, right). If no valid path exists, output -1.

The problem can be mathematically expressed as finding the shortest path such that $$steps = \min_{\text{valid path}} \{\text{number of moves}\}$$ from \((1,1)\) to \((N,M)\).

inputFormat

The input consists of multiple test cases. Each test case begins with a line containing two integers N and M separated by a space. This is followed by N lines, each containing a string of length M representing the grid. The input terminates with a line containing "0 0".

outputFormat

For each test case, output a single line containing one integer: the minimum number of steps required to traverse the grid, or -1 if no path exists.## sample

4 4
....
.##.
..#.
....
4 4
....
####
....
....
0 0

6
-1