题目描述

縦 $H$ マス、横 $W$ マスの $H\times\ W$ マスからなる迷路があります。

上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ は、$S_{ij}$ が # のとき壁であり、.のとき道です。

マス $(C_h,C_w)$ に魔法使いがいます。魔法使いは次の $2$ 種類の方法で移動することができます。

• 移動A：現在いるマスと上下左右に隣接する道のマスへ歩いて移動する。
• 移動B：現在いるマスを中心とする $5\times\ 5$ の範囲内にある道のマスへワープ魔法で移動する。

どちらの行動でも、迷路の外へ移動することはできません。

マス $(D_h,D_w)$ まで移動するには、ワープ魔法を最低で何度使う必要があるでしょうか。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $C_h$ $C_w$ $D_h$ $D_w$ $S_{11}\ldots\ S_{1W}$ $\vdots$ $S_{H1}\ldots\ S_{HW}$

输出格式

ワープ魔法を使う最小回数を出力せよ。$(D_h,D_w)$ に到達不可能な場合、かわりに -1 と出力せよ。

题目大意

• 给定一个迷宫，由 $H$ 行 $W$ 列字符组成，$\texttt{.}$ 可以走，$\texttt{\#}$ 不可以走。
• 有一个人在坐标 $(S_c,S_r)$ 中，每一次他可以向上、下、左、右移动一次。
• 他还可以使用魔法，即直接移动到以他现在的位置为中心的 $5\times 5$ 的正方形中的任意位置。
• 输出这一个人最少使用几次魔法才能到位置 $(E_c,E_r)$。

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

1

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

-1

4 4
2 2
3 3
....
....
....
....

0

4 5
1 2
2 5
#.###
####.
#..##
#..##

2

提示

制約

• $1\ \leq\ H,W\ \leq\ 10^3$
• $1\ \leq\ C_h,D_h\ \leq\ H$
• $1\ \leq\ C_w,D_w\ \leq\ W$
• $S_{ij}$ は # か .
• $S_{C_h\ C_w}$ と $S_{D_h\ D_w}$ は .
• $(C_h,C_w)\ \neq\ (D_h,D_w)$

Sample Explanation 1

例えば $(2,2)$ まで歩いて移動し、$(2,2)$ から $(4,4)$ へワープ魔法で移動することで、ワープ魔法の使用回数を $1$ 回にできます。 歩いて斜めに移動することはできません。

Sample Explanation 2

現在地から動くことができません。

Sample Explanation 3

ワープ魔法を使う必要はありません。