Robot Grid Paths

In this problem, you are given one or more grids along with a set of queries. Each grid is represented by (n) rows and (m) columns, where each cell is either free (represented by a dot, '.') or blocked (represented by a hash, '#'). For each query, you are given the starting cell ((x_1, y_1)) and the destination cell ((x_2, y_2)), and you need to compute the shortest number of moves required for a robot to travel from the start to the destination. The robot can move up, down, left, or right on each move and cannot pass through obstacles. If the destination is unreachable, output (-1).

The distance is defined as the number of moves taken. For example, if the start and the destination are the same cell, the distance is (0).

A common approach to solve this problem is to use Breadth-First Search (BFS), which guarantees the shortest path in an unweighted grid.

inputFormat

Input is read from standard input (stdin) and consists of multiple test cases. The first line contains an integer (T), the number of test cases. For each test case:

• The first line contains two space-separated integers (n) and (m), representing the number of rows and columns of the grid.
• The next (n) lines each contain a string of length (m) representing the grid. A dot ('.') denotes a free cell and a hash ('#') denotes an obstacle.
• The following line contains an integer (q), the number of queries.
• The next (q) lines each contain four space-separated integers (x_1), (y_1), (x_2), and (y_2), indicating the start and destination coordinates (0-indexed) for a robot.

outputFormat

For each test case, output a single line to standard output (stdout) containing (q) space-separated integers. Each integer is the shortest distance from the starting cell to the destination cell for the corresponding query. If there is no valid path, output (-1) for that query.## sample

1
5 5
.....
..#..
....#
.#...
.....
2
0 0 4 4
1 1 3 3

8 4