043 - Maze Challenge with Lack of Sleep(★4)
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 4 点
問題文
縦 H マス、横 W マスのグリッド状の迷路があり、上から i 行目・左から j 列目のマスを (i,j) とします。マス (i,j) は S_{i,j} = #
のとき壁で、S_{i,j} = .
のとき壁ではありません。
あなたは上下左右に隣接する壁でないマスへの移動を繰り返してマス (r_s,c_s) からマス (r_t,c_t) に移動したいです。ただし、移動する方向が変わる回数が多いと脳が疲れてしまうため好ましくありません。また、迷路の外へ出るような移動は許されません。
移動する方向が変わる回数の最小値を求めてください。
制約
- 2 \leq H,W \leq 1000
- 1 \leq r_s,r_t \leq H
- 1 \leq c_s,c_t \leq W
- (r_s,c_s) \ne (r_t,c_t)
- H,W,r_s,c_s,r_t,c_t は整数
- S_{i,j} は
#
または.
- S_{r_s,c_s},S_{r_t,c_t} は
.
- マス (r_s,c_s) からマス (r_t,c_t) への移動が可能
入力
入力は以下の形式で標準入力から与えられます。
H W r_s c_s r_t c_t S_{1,1} S_{1,2} ... S_{1,W} \vdots S_{H,1} S_{H,2} ... S_{H,W}
出力
答えを出力してください。
入力例 1
3 3 1 1 3 3 ..# #.# #..
出力例 1
2
最短路に沿って進むと、マス (1,2) とマス (3,2) で移動の方向が変わります。
入力例 2
3 3 2 1 2 3 #.# ... #.#
出力例 2
0
入力例 3
4 6 2 1 1 5 ...#.. .#.##. .#.... ...##.
出力例 3
5