Shortest Path in a Grid

Given a grid of size \(R \times C\), where each cell is either free space denoted by . or an obstacle denoted by #, your task is to find the shortest path from the top-left corner at \((0,0)\) to the bottom-right corner at \((R-1, C-1)\). You may move in four directions: up, down, left, and right. If there is no valid path, output \(-1\).

The problem can be modeled as a graph where each cell is a node and adjacent free cells are connected by edges. A breadth-first search (BFS) algorithm is an efficient way to solve this problem.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer (T) representing the number of test cases. For each test case, the first line contains two space-separated integers (R) and (C), representing the number of rows and columns respectively. This is followed by (R) lines, each containing a string of length (C) that represents the grid.

outputFormat

For each test case, output a single integer on a new line, which is the length of the shortest path from the start to the destination. If no valid path exists, output (-1). The output should be written to standard output (stdout).## sample

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

4