Minimum Steps to Communicate

This problem involves finding the minimum number of steps required for two animals to communicate in a dense forest represented as a grid. The forest is modeled as an R x C grid where each cell is either an open space (denoted by '.') or a tree (denoted by '#'). The animals can only move to adjacent open cells in the four cardinal directions (up, down, left, right).

If there is a path from the first animal's starting position \((r_1, c_1)\) to the second animal's position \((r_2, c_2)\), output the minimum number of steps required. Otherwise, output -1.

The movement rule can be mathematically represented as follows:

[ steps = \min { d(p, q) \mid p,q \text{ are adjacent and reachable from the start to the end} } ]

Use an appropriate breadth-first search (BFS) algorithm to solve this problem.

inputFormat

The first line contains a single integer T representing the number of test cases. Each test case is described as follows:

• The first line contains two integers R and C, the number of rows and columns of the grid.
• The next R lines each contain a string of length C representing the grid, where . denotes an open space and # denotes a tree.
• The next line contains four integers: r1, c1, r2, c2 representing the 0-indexed starting positions of the two animals.

The input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing one integer: the minimum number of steps required for the first animal to reach the second. If communication is impossible, output -1.

The output should be printed to standard output (stdout).

## sample

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

6
-1
-1

</p>