Minimum Steps to Destination in a City Grid

You are given a square grid representing a city map, where each cell is either a . (open road) or a # (obstacle). A car is initially positioned at a given cell and needs to reach a specified destination cell. The car can move in four directions: up, down, left, and right.

Your task is to determine the minimum number of steps required for the car to reach the destination. If the destination is not reachable, output -1.

The problem can be modeled as a breadth-first search (BFS) on a grid. The number of steps can be expressed using the formula:

\(steps = d(s, t)\), where \(d(s, t)\) is the length of the shortest path from the starting point \(s\) to the target \(t\). If no such path exists, return \(-1\).

inputFormat

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

T
n
row_1
row_2
... 
row_n
sx sy
dx dy
... (repeated for T test cases)

Here:

• T is the number of test cases.
• For each test case, the first line contains an integer n indicating the size of the grid.
• The next n lines each contain a string of length n representing the grid. Each character is either . (open road) or # (obstacle).
• The next line contains two integers sx and sy, the starting coordinates (0-indexed).
• The final line for the test case contains two integers dx and dy, the destination coordinates (0-indexed).

outputFormat

For each test case, print a single line containing the minimum number of steps needed for the car to reach the destination from the starting point. If the destination is unreachable, print -1.

## sample

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

6
-1

</p>