Shortest Path in a Warehouse Grid

You are given a grid of warehouses where each cell can either be open or blocked. The helicopter, starting from a given warehouse, needs to deliver goods to a destination warehouse.

The grid is represented as an N × M matrix where each cell is either . (open) or # (blocked). The helicopter can move in the four cardinal directions: up, down, left, or right. Each move costs 1 unit of time. Note that moving diagonally is not allowed.

Your task is to compute the minimum time needed for the helicopter to travel from the start cell to the destination cell. If there is no valid path, output -1.

The movement cost is given by \(1\) per move. The constraints are given by: \[ 1 \leq T \leq 10,\quad 1 \leq N, M \leq 1000 \]

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer T, the number of test cases.
• For each test case:
  • A line containing two integers N and M, the number of rows and columns in the grid.
  • Next N lines each containing a string of M characters. Each character is either . (open cell) or # (blocked cell).
  • A line containing two integers sx and sy, the starting cell coordinates (0-indexed).
  • A line containing two integers dx and dy, the destination cell coordinates (0-indexed).

outputFormat

For each test case, output a single integer on a new line representing the minimum time required to reach the destination from the start. If the destination cannot be reached, output -1.

## sample

1
5 5
.....
..#..
..#..
.....
.....
0 0
4 4

8

</p>