题目描述

有一个 $N \times N$ 的国际象棋棋盘。棋盘上从上往下第 $i$ 行，从左往右第 $j$ 列的格子称为格子 $(i, j)$。
棋盘的信息以 $N$ 个字符串 $S_i$ 给出。
字符串 $S_i$ 的第 $j$ 个字符 $S_{i,j}$ 包含以下信息：

• 当 $S_{i,j} = \texttt{.}$ 时，格子 $(i, j)$ 上没有任何棋子。
• 当 $S_{i,j} = \texttt{\#}$ 时，格子 $(i, j)$ 上有一个白色兵（pawn）。这个兵不能被移动或移除。

现在在棋盘的格子 $(A_x, A_y)$ 上放置了一个白色主教（bishop）。
请你求出，按照国际象棋的规则（见下方注释），将这个主教从 $(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)$ 上的白色主教可以按照以下规则每一步移动：

• 对于每个正整数 $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) \ne (B_x, B_y)$
• $S_i$ 是由 . 和 # 组成的长度为 $N$ 的字符串
• $S_{A_x, A_y} = \texttt{.}$
• $S_{B_x, B_y} = \texttt{.}$

样例解释 1

如下图所示，可以通过 $3$ 步将主教从 $(1, 3)$ 移动到 $(3, 5)$。无法在 $2$ 步以内完成。

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

样例解释 2

无论如何移动主教，都无法将其从 $(3, 2)$ 移动到 $(4, 2)$。