AT_abc176_d [ABC176D] Wizard in Maze

[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) $ まで移動するには、ワープ魔法を最低で何度使う必要があるでしょうか。

N/A

N/A

### 制約 - $ 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 ワープ魔法を使う必要はありません。