Minimum Steps for Drone Navigation

You are given an n × n grid representing a map where each cell is either . (an open space) or # (an obstacle). Starting from position (sx, sy), you must determine the minimum number of moves required to reach the target position (tx, ty).

The drone can move in four directions: up, down, left, and right. Moves cannot pass through obstacles or outside the grid. If there is no valid path from the starting point to the target point, output -1.

Note: The grid positions are provided using 1-based indexing.

The problem can be formalized as follows:

Given an integer \(n\), a grid \(G\) of dimensions \(n\times n\) where each cell \(G_{ij}\) is either \(\texttt{.}\) or \(\texttt{#}\), and integers \(sx, sy, tx, ty\) indicating the start and target positions respectively, find the minimum number of moves needed to go from \((sx, sy)\) to \((tx, ty)\). If the target is unreachable, print \(-1\).

Constraints:

• \(1 \le n \le 1000\)
• Each grid row is a string of length \(n\) containing only \(\texttt{.}\) and \(\texttt{#}\).
• \(1 \le sx, sy, tx, ty \le n\)

inputFormat

The input is read from stdin and consists of:

1. An integer n, the size of the grid.
2. n lines each containing a string of length n representing the grid row (each character is either . or #).
3. A single line with four integers: sx sy tx ty, corresponding to the starting and target positions (1-based indexes).

outputFormat

Output a single integer to stdout:

• The minimum number of moves to reach the target, or -1 if the target is not reachable.

## sample

5
.....
..#..
.....
..#..
.....
1 1 5 5

8

</p>