/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
縦 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) まで移動するには、ワープ魔法を最低で何度使う必要があるでしょうか。
制約
- 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)
入力
入力は以下の形式で標準入力から与えられる。
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 と出力せよ。
入力例 1
4 4 1 1 4 4 ..#. ..#. .#.. .#..
出力例 1
1
例えば (2,2) まで歩いて移動し、(2,2) から (4,4) へワープ魔法で移動することで、ワープ魔法の使用回数を 1 回にできます。
歩いて斜めに移動することはできません。
入力例 2
4 4 1 4 4 1 .##. #### #### .##.
出力例 2
-1
現在地から動くことができません。
入力例 3
4 4 2 2 3 3 .... .... .... ....
出力例 3
0
ワープ魔法を使う必要はありません。
入力例 4
4 5 1 2 2 5 #.### ####. #..## #..##
出力例 4
2
Score : 400 points
Problem Statement
A maze is composed of a grid of H \times W squares - H vertical, W horizontal.
The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..
There is a magician in (C_h,C_w). He can do the following two kinds of moves:
- Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.
- Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.
In either case, he cannot go out of the maze.
At least how many times does he need to use the magic to reach (D_h, D_w)?
Constraints
- 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} is
#or.. - S_{C_h C_w} and S_{D_h D_w} are
.. - (C_h,C_w) \neq (D_h,D_w)
Input
Input is given from Standard Input in the following format:
H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}
Output
Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.
Sample Input 1
4 4 1 1 4 4 ..#. ..#. .#.. .#..
Sample Output 1
1
For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.
Note that he cannot walk diagonally.
Sample Input 2
4 4 1 4 4 1 .##. #### #### .##.
Sample Output 2
-1
He cannot move from there.
Sample Input 3
4 4 2 2 3 3 .... .... .... ....
Sample Output 3
0
No use of magic is needed.
Sample Input 4
4 5 1 2 2 5 #.### ####. #..## #..##
Sample Output 4
2