[ABC176D] Wizard in Maze
题意翻译
- 给定一个迷宫,由 $H$ 行 $W$ 列字符组成,$\texttt{.}$ 可以走,$\texttt{\#}$ 不可以走。
- 有一个人在坐标 $(S_c,S_r)$ 中,每一次他可以向上、下、左、右移动一次。
- 他还可以使用魔法,即直接移动到以他现在的位置为中心的 $5\times 5$ 的正方形中的任意位置。
- 输出这一个人最少使用几次魔法才能到位置 $(E_c,E_r)$。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc176/tasks/abc176_d
縦 $ 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` と出力せよ。
输入输出样例
输入样例 #1
4 4
1 1
4 4
..#.
..#.
.#..
.#..
输出样例 #1
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
说明
### 制約
- $ 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
ワープ魔法を使う必要はありません。