#abc176d. [abc176_d]Wizard in Maze

[abc176_d]Wizard in Maze

問題文

HH マス、横 WW マスの HtimesWH\\times W マスからなる迷路があります。

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

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

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

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

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

制約

  • 1leqH,Wleq1031 \\leq H,W \\leq 10^3
  • 1leqCh,DhleqH1 \\leq C_h,D_h \\leq H
  • 1leqCw,DwleqW1 \\leq C_w,D_w \\leq W
  • SijS_{ij}#.
  • SChCwS_{C_h C_w}SDhDwS_{D_h D_w}.
  • (Ch,Cw)neq(Dh,Dw)(C_h,C_w) \\neq (D_h,D_w)

入力

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

HH WW ChC_h CwC_w DhD_h DwD_w S11ldotsS1WS_{11}\\ldots S_{1W} vdots\\vdots SH1ldotsSHWS_{H1}\\ldots S_{HW}

出力

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


入力例 1

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

出力例 1

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

歩いて斜めに移動することはできません。


入力例 2

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

出力例 2

-1

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


入力例 3

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

出力例 3

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


入力例 4

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

出力例 4