配点 : $500$ 点

コンテスト開催当時はメモリ制限が2GBでしたが、ジャッジ環境が異なるため、現在はメモリ制限を1GBに設定しております。なお、このメモリ制限でもAC出来ることは確認しています。

問題文

ここに、 $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 を出力してください。

注記

マス $(i,j)$ に置かれている白の ビショップ

は、 $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}=$ .

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_x$ $A_y$

$B_x$ $B_y$

$S_1$

$S_2$

$\vdots$

$S_N$

出力

答えを出力せよ。

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

3

以下のように移動させることで $3$ 手でビショップを $(1,3)$ から $(3,5)$ まで移動させることができます。 $2$ 手以内でビショップを $(1,3)$ から $(3,5)$ まで移動させることはできません。

• $(1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)$

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

-1

どのようにビショップを動かしても $(3,2)$ から $(4,2)$ に移動させることはできません。

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

9