RoboDeliver: Minimum Time to Reach Target

RoboDeliver is a smart delivery robot that has to deliver packages by moving on a square grid. The grid is of size (n \times n) and each cell is either free (represented by 0) or blocked by an obstacle (represented by 1). RoboDeliver can move one step at a time in any of the four cardinal directions (up, down, left, and right). The objective is to determine the minimum number of moves required for RoboDeliver to travel from the starting cell ((s_x, s_y)) to the target cell ((t_x, t_y)). If it is impossible to reach the destination, output -1.

The movement cost is uniform; thus, if RoboDeliver makes (k) moves, then the time taken is (k). Use Breadth-First Search (BFS) to solve this problem efficiently.

inputFormat

The input begins with an integer (T) on the first line, representing the number of test cases. The description of each test case is as follows:

• The first line contains a single integer (n) ((1 \leq n \leq 1000)), denoting the size of the grid.
• The next (n) lines each contain (n) integers separated by spaces, describing the grid (0 for free cells and 1 for obstacles).
• The last line of each test case contains four integers: (s_x), (s_y), (t_x), (t_y) (0-indexed), representing the starting coordinates and the target coordinates respectively.

All input is provided via standard input (stdin).

outputFormat

For each test case, print a single line containing the minimum number of moves required for RoboDeliver to reach the target cell. If the destination is unreachable, print -1. All output should be sent to standard output (stdout).## sample

3
0 0 0
0 1 0
0 0 0
0 0 2 2

4