当前没有测试数据。

E - 主教 2

分数：500分

问题描述

我们有一个$N \times N$的棋盘，用$N$个字符串$S_i$来表示棋盘，其中$N$表示棋盘的大小。

每一个字符$S_{i,j}$表示以下情况：

• 如果$S_{i,j} =$ `.`，则表示$(i, j)$的格子为空。
• 如果$S_{i,j} =$ `#`，则表示$(i, j)$的格子上有一个白色的兵，不能移动或删除。

我们在棋盘的 $(A_x, A_y)$ 处放了一只白色的主教。
请找出从主教的初始位置$(A_x, A_y)$移动到目标位置 $(B_x, B_y)$的最小移动次数（根据国际象棋规则进行移动）。
如果无法移动到 $(B_x, B_y)$，则报告-1。

解释

在国际象棋中，主教可以按以下规则移动：

• 对于每个正整数$d$，它可以移动到 $(i+d,j+d)$（对角线向右下移动），如果满足以下条件：

  • 棋盘上存在$(i+d,j+d)$这个格子。
  • 对于所有小于等于$d$的正整数$l$，$(i+l,j+l)$这个格子没有被白色兵占据。

• 对于每个正整数$d$，它可以移动到 $(i+d,j-d)$（对角线向右上移动），如果满足以下条件：

  • 棋盘上存在$(i+d,j-d)$这个格子。
  • 对于所有小于等于$d$的正整数$l$，$(i+l,j-l)$这个格子没有被白色兵占据。

• 对于每个正整数$d$，它可以移动到 $(i-d,j+d)$（对角线向左下移动），如果满足以下条件：

  • 棋盘上存在$(i-d,j+d)$这个格子。
  • 对于所有小于等于$d$的正整数$l$，$(i-l,j+l)$这个格子没有被白色兵占据。

• 对于每个正整数$d$，它可以移动到 $(i-d,j-d)$（对角线向左上移动），如果满足以下条件：

  • 棋盘上存在$(i-d,j-d)$这个格子。
  • 对于所有小于等于$d$的正整数$l$，$(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

我们可以按照以下方式将主教从 $(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
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................