AT_abc400_d [ABC400D] Takahashi the Wall Breaker

高橋君は魚屋にウナギを買いに行こうとしています。 高橋君の住む町は縦 $ H $ マス横 $ W $ マスからなるグリッド状の区画に分かれており、 各区画は道か壁かのいずれかです。 以下、上から $ i $ 番目 $ (1\leq i \leq H) $ かつ左から $ j $ 番目 $ (1\leq j\leq W) $ の区画を区画 $ (i,j) $ で表します。 各区画の情報は $ H $ 個の長さ $ W $ の文字列 $ S_1,S_2,\ldots,S_H $ で与えられ、 具体的には $ S_i $ の $ j $ 文字目 $ (1\leq i \leq H,1\leq j\leq W) $ が `.` のとき区画 $ (i,j) $ が道であることを、 $ S_i $ の $ j $ 文字目が `#` のとき区画 $ (i,j) $ が壁であることを表します。 高橋君は次の $ 2 $ 種類の行動を好きな順番で繰り返し行うことができます。 - 上下左右に隣接する、町の中の区画であって、道であるようなものに移動する。 - 上下左右の方向を一つ決め、その方向に**前蹴り**を行う。 高橋君が前蹴りを行うと、現在いる区画からその方向に $ 1 $ つ前の区画および $ 2 $ つ前の区画について、その区画が壁ならば道に変えることができる。 ここで、 $ 1 $ つ前の区画または $ 2 $ つ前の区画が町の外である場合でも前蹴りを行うことができるが、町の外が変化することはない。 高橋君は最初、区画 $ (A,B) $ におり、区画 $ (C,D) $ にある魚屋まで移動したいです。 ここで、高橋君の最初にいる区画および魚屋のある区画は道であることが保証されます。 高橋君が魚屋にたどり着くために必要な **前蹴りの回数** の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $ $ A $ $ B $ $ C $ $ D $

高橋君が魚屋にたどり着くために必要な **前蹴りの回数** の最小値を出力せよ。

### Sample Explanation 1 高橋君は最初、区画 $ (1,1) $ にいます。 道である区画への移動を繰り返して区画 $ (7,4) $ まで移動することができます。 区画 $ (7,4) $ において左方向に対して前蹴りを行うと区画 $ (7,3) $ と区画 $ (7,2) $ が壁から道に変わります。 その後、道である区画（道に変わった区画を含む）への移動を繰り返して、区画 $ (7,1) $ にある魚屋に移動することができます。 このとき、前蹴りを行った回数は $ 1 $ 回であり、前蹴りを行わずに魚屋へ移動することは不可能なため、 $ 1 $ を出力します。 ### Sample Explanation 2 高橋君は最初、区画 $ (1,1) $ にいます。 右方向に対して前蹴りを行うと、区画 $ (1,2) $ を壁から道に変えることができます。 区画 $ (1,1) $ から右方向に $ 2 $ つ前のマスは町の外であるため、変化しません。 その後、高橋君は区画 $ (1,2) $ へ移動し、区画 $ (2,2) $ にある魚屋へ移動することができます。 このとき、前蹴りを行った回数は $ 1 $ 回であり、前蹴りを行わずに魚屋へ移動することは不可能なため、 $ 1 $ を出力します。 ### Sample Explanation 3 前蹴りを行う際、それにより道に変えられ得る区画の中に魚屋のある区画が含まれていても問題ありません。 具体的には魚屋のある区画はもともと道であるため変化せず、特に前蹴りによって魚屋が壊れることはありません。 ### Constraints - $ 1\leq H\leq 1000 $ - $ 1\leq W\leq 1000 $ - $ S_i $ は `.`, `#` のみからなる長さ $ W $ の文字列 - $ 1\leq A,C\leq H $ - $ 1\leq B,D\leq W $ - $ (A,B)\neq (C,D) $ - $ H,W,A,B,C,D $ は整数 - 高橋君の最初にいる区画および魚屋のある区画は道である。