[ABC246E] Bishop 2

给定有障碍的网格图，`.` 为空地，`#` 为障碍。给定起点终点，每次移动仅可以斜向走任意长度，问从起点到终点的最少移动次数，可能无解，无解输出 `-1`。

[problemUrl]: https://atcoder.jp/contests/abc246/tasks/abc246_e ここに、 $ N\ \times\ N $ のチェス盤があります。このチェス盤の上から $ i $ 行目、左から $ j $ 列目にあるマスをマス $ (i,j) $ と呼びます。 チェス盤の情報は $ N $ 個の文字列 $ S_i $ として与えられます。 文字列 $ S_i $ の $ j $ 文字目である $ S_{i,j} $ には、以下の情報が含まれています。 - $ S_{i,j}= $ `.` のとき マス $ (i,j) $ には何も置かれていない。 - $ S_{i,j}= $ `#` のとき マス $ (i,j) $ には白のポーンが $ 1 $ つ置かれている。このポーンを動かしたり取り除いたりすることはできない。 この盤面のマス $ (A_x,A_y) $ に、白のビショップを $ 1 $ つ置きました。 この白のビショップをチェスのルール (注記参照) に従ってマス $ (A_x,A_y) $ からマス $ (B_x,B_y) $ に移動させるために必要な最小の手数を求めてください。 ただし、移動できない場合は代わりに `-1` を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_x $ $ A_y $ $ B_x $ $ B_y $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

答えを出力せよ。

5
1 3
3 5
....#
...#.
.....
.#...
#....

3

4
3 2
4 2
....
....
....
....

-1

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

9

### 注記 マス $ (i,j) $ に置かれている白の [ビショップ](https://ja.wikipedia.org/wiki/%E3%83%93%E3%82%B7%E3%83%A7%E3%83%83%E3%83%97) は、 $ 1 $ 手で以下のルールに従って移動することができます。 - 各正整数 $ d $ について、以下の条件を全て満たせばマス $ (i+d,j+d) $ に移動できる。 - マス $ (i+d,j+d) $ が盤内に存在する - 全ての正整数 $ l\ \le\ d $ について、 $ (i+l,j+l) $ に白のポーンがない - 各正整数 $ d $ について、以下の条件を全て満たせばマス $ (i+d,j-d) $ に移動できる。 - マス $ (i+d,j-d) $ が盤内に存在する - 全ての正整数 $ l\ \le\ d $ について、 $ (i+l,j-l) $ に白のポーンがない - 各正整数 $ d $ について、以下の条件を全て満たせばマス $ (i-d,j+d) $ に移動できる。 - マス $ (i-d,j+d) $ が盤内に存在する - 全ての正整数 $ l\ \le\ d $ について、 $ (i-l,j+l) $ に白のポーンがない - 各正整数 $ d $ について、以下の条件を全て満たせばマス $ (i-d,j-d) $ に移動できる。 - マス $ (i-d,j-d) $ が盤内に存在する - 全ての正整数 $ l\ \le\ d $ について、 $ (i-l,j-l) $ に白のポーンがない ### 制約 - $ 2\ \le\ N\ \le\ 1500 $ - $ 1\ \le\ A_x,A_y\ \le\ N $ - $ 1\ \le\ B_x,B_y\ \le\ N $ - $ (A_x,A_y)\ \neq\ (B_x,B_y) $ - $ S_i $ は `.` および `#` からなる $ N $ 文字の文字列 - $ S_{A_x,A_y}= $ `.` - $ S_{B_x,B_y}= $ `.` ### Sample Explanation 1 以下のように移動させることで $ 3 $ 手でビショップを $ (1,3) $ から $ (3,5) $ まで移動させることができます。 $ 2 $ 手以内でビショップを $ (1,3) $ から $ (3,5) $ まで移動させることはできません。 - $ (1,3)\ \rightarrow\ (2,2)\ \rightarrow\ (4,4)\ \rightarrow\ (3,5) $ ### Sample Explanation 2 どのようにビショップを動かしても $ (3,2) $ から $ (4,2) $ に移動させることはできません。