Taco Pathfinding Challenge

You are given a grid consisting of . (free cell) and # (obstacle). Your task is to determine the minimum number of steps required to move from the top-left corner of the grid (cell (0,0)) to the bottom-right corner (cell (n-1, m-1)). Movement is allowed in the four cardinal directions: up, down, left, and right. If the destination is not reachable, output -1.

Note that the minimum number of steps in a grid with no obstacles is at least the Manhattan distance, which is given by \( |n-1-0| + |m-1-0| \). However, obstacles may force a longer path if a direct route is blocked.

Input/Output Details: The input is read from standard input (stdin) and output is written to standard output (stdout).

inputFormat

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

Example:

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

outputFormat

For each test case, output the minimum number of steps required to reach the bottom-right corner from the top-left corner. If the destination is unreachable, output -1. Each result should be printed on a new line.

Example Output:

4
6

## sample

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

4
6

</p>