/ 
実行時間制限: 3.5 sec / メモリ制限: 1024 MB
問題文
縦 H マス、横 W マスの H×W マスからなる迷路があります。
上から i 行目、左から j 列目のマス (i,\ j) は、S_{i,j} が #
のとき壁であり、. のとき道です。
マス (sx,\ sy) にうなぎがいて、マス (gx,\ gy) まで移動しようとしています。 うなぎは 1 回の移動で、今いるマスと隣接する道マスに移動することができます。この際、迷路の外への移動はできません。
うなぎはくねくね動くのが好きです。そこで、迷路をプレイする際に以下の制限を設けることにしました。
- i 回目の移動で上下に移動した場合、i+1 回目の移動では左右に移動しなければならない。
- i 回目の移動で左右に移動した場合、i+1 回目の移動では上下に移動しなければならない。
- 最初の移動では、どの方向にも動くことができる。
うなぎはこの制限を守った上で、マス (gx,\ gy) まで移動できるでしょうか？ 移動できるか判定した上で、移動できる場合は必要な移動回数の最小値を求めてください。
制約
- 1\leq H,\ W\leq2000
- 1\leq sx,\ gx\leq H
- 1\leq sy,\ gy\leq W
- S_{i,j} は
#か. - S_{sx,sy} と S_{gx,gy} は
. - (sx,\ sy)≠(gx,\ gy)
- H,\ W,\ sx,\ sy,\ gx,\ gy は整数
入力
入力は以下の形式で標準入力から与えられます。
\(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}\)
出力
うなぎがマス (gx,\ gy) まで移動できる場合は移動回数の最小値を、移動できない場合は -1 を出力してください。 出力の最後に改行を忘れないでください。
入力例1
2 3 1 1 1 3 ... ..#
出力例1
4
(1,\ 1)\ →\ (2,\ 1)\ →\ (2,\ 2)\ →\ (1,\ 2)\ →\ (1,\ 3) と移動するのが最適です。
入力例2
3 4 1 1 3 4 .... .#.. ....
出力例2
-1
どう移動してもマス (3,\ 4) まで移動できません。
入力例3
5 7 4 1 5 4 .#..#.. #....#. ...#..# .#..... ..#..#.
出力例3
14