Taco Maze

In this problem, you are given one or more grid maps where each grid consists of rows of characters. Each cell in the grid is either a free space denoted by a dot ('.') or an obstacle denoted by a hash ('#'). 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)) moving only up, down, left, or right. If no valid path exists, output -1.

The problem can be formalized as follows:

Given a grid with dimensions ( n \times m ), find the minimum number of moves required to reach from cell ( (1,1) ) to cell ( (n,m) ) without stepping into obstacles. Use the standard Breadth-first Search (BFS) approach to solve it efficiently.

Input Constraints:\newline Each test input starts with an integer ( t ) representing the number of test cases. For each test case, the first line contains two integers ( n ) and ( m ), followed by ( n ) lines each containing a string of length ( m ) representing the grid.

Note: For grids where the starting or ending position is an obstacle, the answer is (-1).

inputFormat

The input is given via standard input (stdin). The first line contains an integer ( t ) (the number of test cases). Then, for each test case, the first line contains two integers ( n ) and ( m ) (the number of rows and columns). Following this, there are ( n ) lines each consisting of a string of length ( m ) that represents the grid.

outputFormat

For each test case, output a single line with one integer: the length of the shortest path from the top-left corner to the bottom-right corner. If no such path exists, output (-1). The output should be printed to standard output (stdout).## sample

1
5 5
.....
.#.#.
.#.#.
.#.#.
.....

8