Bishop 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$。

输入格式

输入按下列格式由标准输入提供： $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

提示

$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}=$ $.$位于格子 $(i, j)$ 的白色主教在一次走子中可以走到以下位置。

对于任意正整数 $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)$ 上没有白兵占据。我们可以按如下三步将主教从 $(1,3)$ 移到 $(3,5)$，但无法在两步或更少步数内完成。

$(1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)$
没有办法将主教从 $(3,2)$ 移到 $(4,2)$。

标签: AtCoder|abc246E

来源

AtCoder|abc246E