Problem Description

Score: $ 400 $ points

There is a maze consisting of $ H $ rows and $ W $ columns, forming an $ H×W $ grid. The cell $(i,\ j)$ at the $ i $ -th row from the top and the $ j $ -th column from the left is a wall if $ S_{i,j} $ is #, and a path if $ S_{i,j} $ is ..

An eel is located at cell $(sx,\$ and is trying to move to cell $(gx,\$. The eel can move to an adjacent path cell in one move, but cannot move outside the maze.

The eel likes to move wiggly. Therefore, the following restrictions are imposed while playing the maze:

• If the $ i $ -th move is vertical, the $ i+1 $ -th move must be horizontal.
• If the $ i $ -th move is horizontal, the $ i+1 $ -th move must be vertical.
• The first move can be in any direction.

Can the eel move to cell $(gx,\$ while adhering to these restrictions? Determine if it is possible and, if so, find the minimum number of moves required.

Input Format

The input is given from the standard input in the following format:

\(H\) \(W\)
\(sx\) \(sy\) \(gx\) \(gy\)
\(S_{1,1}\) \(S_{1,2}\) \(\ldots\) \(S_{1,W}\)
\(S_{2,1}\) \(S_{2,2}\) \(\ldots\) \(S_{2,W}\)
\(⋮\)
\(S_{H,1}\) \(S_{H,2}\) \(\ldots\) \(S_{H,W}\)

Output Format

If the eel can move to cell $(gx,\$, output the minimum number of moves; otherwise, output $ -1 $. Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

2 3
1 1 1 3
...
..#

Sample Output #1

4

Sample Input #2

3 4
1 1 3 4
....
.#..
....

Sample Output #2

-1

Sample Input #3

5 7
4 1 5 4
.#..#..
#....#.
...#..#
.#.....
..#..#.

Sample Output #3

14

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分