Taco Grid Navigation Challenge

In this problem, you are given an n×m grid representing a map. Each cell in the grid is either open (denoted by '.') or blocked by an obstacle (denoted by '#'). A robot is placed at a starting cell and needs to move to a target cell. The robot can move one step at a time in any of the four cardinal directions (up, down, left, right). Your task is to determine the minimum number of moves required for the robot to reach the target cell. If the target cell is not reachable, output -1.

Note: The grid positions are provided in 1-indexed format. The grid description uses space separated symbols for each row.

The movement is allowed only on open cells ('.') and the robot cannot move through obstacles ('#').

The mathematical formulation for the number of moves is simply the length of the shortest path between the starting cell \( (x_1, y_1) \) and the target cell \( (x_2, y_2) \), which can be computed using breadth-first search (BFS). If no such path exists, the answer is \(-1\).

inputFormat

The input is read from standard input (stdin) and has the following format:

n m t
x1 y1 x2 y2
row1
row2
... (n rows in total)
... (repeat the above block for t test cases)

Where:

• n is the number of rows in the grid.
• m is the number of columns in the grid.
• t is the number of test cases.
• For each test case, the first line contains four integers: x1, y1, x2, y2 representing the starting position and target position (1-indexed).
• Then follow n lines each containing m symbols (each symbol separated by a space) representing the grid. A '.' indicates an open cell and a '#' indicates an obstacle.

outputFormat

For each test case, output the minimum number of moves required for the robot to reach the target cell. If it is not possible to reach the target cell, output -1. Each result must be printed on a new line to standard output (stdout).

## sample

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

3
-1

</p>