Shortest Path in Grid

You are given a grid of size \(N \times M\) that represents a map where each cell is either . (an open space) or # (a building/obstacle). Your task is to determine the shortest number of moves required to travel from the top-left corner (cell (1, 1)) to the bottom-right corner (cell (N, M)) while only moving up, down, left or right. If it is impossible to reach the destination, output \(-1\).

Note: The move count does not include the starting cell. If the grid contains only one cell and it is open, the answer is 0.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\), the number of test cases. Each test case starts with a line containing two integers, \(N\) and \(M\), representing the number of rows and columns in the grid. This is followed by \(N\) lines, each containing a string of length \(M\) composed of characters . and #.

outputFormat

For each test case, print a single integer representing the length of the shortest path from the top-left corner to the bottom-right corner. If no valid path exists, print -1. The output for each test case should be on a new line.

1
3 3
...
.#.
...

4