题目描述

ここに、 $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$

输出格式

答えを出力せよ。

题目大意

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

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

3

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

-1

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

9

提示

注記

マス $(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}=$ .

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)$ に移動させることはできません。