Shortest Path in a Grid

Given a grid with n rows and m columns, where each cell is either a free cell ('.') or an obstacle ('#'), determine the minimum number of moves required to travel from the top-left corner to the bottom-right corner. Movement is allowed to adjacent cells in four directions: up, down, left, and right. If either the starting or ending cell is blocked or no valid path exists, the answer should be -1. The distance is defined as the number of moves taken, where moving from one cell to an adjacent cell counts as one move. This problem may include multiple test cases.

Note: If the grid size is 1x1 and the cell is free, then no move is required (distance is 0). All indices are 0-indexed.

inputFormat

The input begins with an integer T, representing the number of test cases. For each test case, the first line contains two space-separated integers n and m, denoting the number of rows and columns of the grid, respectively. This is followed by n lines, each containing a string of m characters (each either '.' or '#') representing the grid.

outputFormat

For each test case, output a single integer on a new line indicating the minimum number of moves required to reach the bottom-right cell from the top-left cell. If there is no valid path, output -1.

3
3 3
.#.
...
#..
2 2
..
#.
3 3
.#.
###
.#.

4
2
-1