Maze Shortest Path

You are given a maze represented as a grid of N rows and M columns. Each cell is either . (an open path) or # (a wall). You are also given the starting position (sx, sy) and the ending position (ex, ey).

Your task is to compute the length of the shortest path from the start to the end. You may move in four directions: up, down, left, and right, but you cannot move diagonally. If no valid path exists, output -1.

The movement is subject to the constraint that the new position must remain within the grid and be accessible (i.e. a .). The problem can be modeled using a breadth-first search (BFS) algorithm. For example, if we denote the step counter by s, then the relation for adjacent steps is given by: $$s_{next} = s+1$$

Note that if the start and end positions are identical, the answer is 0.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two integers N and M \( (1 \leq N, M \leq 1000) \)</code>, representing the number of rows and columns of the maze.
2. The second line contains four integers: sx sy ex ey, where (sx, sy) is the starting position and (ex, ey) is the ending position. Positions are zero-indexed.
3. The next N lines each contain a string of length M consisting only of the characters . and #, which represent an open path and a wall respectively.

outputFormat

The output is a single integer printed to standard output (stdout). This integer is the length of the shortest path from the start to the end. If there is no possible path, print -1.

## sample

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

8

</p>