主教 2

题目描述

我们有一个 $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)$ 被一个白色兵占据,该兵无法移动或移除。

我们把一个白色主教放在格子 $(A_x, A_y)$ 上。

求出按照国际象棋的规则(见下注)把该主教从 $(A_x, A_y)$ 移动到 $(B_x, B_y)$ 所需的最少步数。

如果无法移动到 $(B_x, B_y)$,则输出 -1。

注:一个位于格子 $(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)$ 均未被白色兵占据。

输入格式

输入按以下格式从标准输入给出:

N
A_x A_y
B_x B_y
S_1
S_2
⋮
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
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

9

数据范围

• $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}$ 为 .。