AT_pakencamp_2020_day1_i くねくね

[problemUrl]: https://atcoder.jp/contests/pakencamp-2020-day1/tasks/pakencamp_2020_day1_i 配点 : $ 400 $ 点 縦 $ H $ マス、横 $ W $ マスの $ H×W $ マスからなる迷路があります。 上から $ i $ 行目、左から $ j $ 列目のマス $ (i,\ j) $ は、$ S_{i,j} $ が `#` のとき壁であり、`.` のとき道です。 マス $ (sx,\ sy) $ にうなぎがいて、マス $ (gx,\ gy) $ まで移動しようとしています。 うなぎは $ 1 $ 回の移動で、今いるマスと隣接する道マスに移動することができます。この際、迷路の外への移動はできません。 うなぎはくねくね動くのが好きです。そこで、迷路をプレイする際に以下の制限を設けることにしました。 - $ i $ 回目の移動で上下に移動した場合、$ i+1 $ 回目の移動では左右に移動しなければならない。 - $ i $ 回目の移動で左右に移動した場合、$ i+1 $ 回目の移動では上下に移動しなければならない。 - 最初の移動では、どの方向にも動くことができる。 うなぎはこの制限を守った上で、マス $ (gx,\ gy) $ まで移動できるでしょうか？ 移動できるか判定した上で、移動できる場合は必要な移動回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられます。 ``` \(H\) \(W\) \(sx\) \(sy\) \(gx\) \(gy\) \(S_{1,1}\) \(S_{1,2}\) \(\ldots\) \(S_{1,W}\) \(S_{2,1}\) \(S_{2,2}\) \(\ldots\) \(S_{2,W}\) \(⋮\) \(S_{H,1}\) \(S_{H,2}\) \(\ldots\) \(S_{H,W}\) ```

うなぎがマス $ (gx,\ gy) $ まで移動できる場合は移動回数の最小値を、移動できない場合は $ -1 $ を出力してください。 出力の最後に改行を忘れないでください。