Shortest Path in a Grid

Alyssa needs a program to calculate the minimum number of steps required to go from a starting point to a destination in a grid. The grid is represented as an n x n matrix of characters, where a dot (.) represents an open cell and a hash (#) represents an obstacle. You can move in four directions: up, down, left, and right. The task is to compute the shortest path length while avoiding obstacles. If no path exists, output -1. Note that if the starting point is the same as the destination, the answer is 0.

The movement in the grid can be described by the following formula in LaTeX:

$$ \text{distance} = \min\{ \text{steps} \;|\; \text{valid path from } (sx,sy) \text{ to } (dx,dy) \} $$

inputFormat

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

n
sx sy
dx dy
row1
row2
...
rown

</p>

Where:

• n is the size of the grid (an integer).
• sx and sy are the starting row and column indices (0-indexed).
• dx and dy are the destination row and column indices (0-indexed).
• Each of the next n lines represents a row of the grid consisting of . (open cell) and # (obstacle).

outputFormat

Output a single integer to stdout representing the shortest number of steps to travel from the starting position to the destination. If no valid path exists, output -1.

## sample

4
0 0
3 3
....
....
....
....

6