分数: 500 点
比赛期间,内存限制设置为2GB。不过,由于评审环境发生变化,内存限制现已设置为1GB。请注意,已确认解决方案仍然可以在此内存限制内实现可接受的完成 (AC)。
问题陈述
我们有一个 N \times N 棋盘。让 (i, j) 表示位于 i从顶部开始的第行和 j此板左侧的第列。
该板的描述为 N 字符串 S_i.
的 j- 字符串的第一个字符 S_i, S_{i,j},含义如下。
- If S_{i,j}=
.,正方形 (i, j) 为空。 - If S_{i,j}=
#,正方形 (i, j) 被一个白色棋子占据,无法移动或移除。
我们在广场上放置了一个白色主教 (A_x, A_y).
找出将该主教从 (A_x, A_y) to (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) 未被白棋子占据。
约束
- 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
输出
打印答案。
示例输入 1
5 1 3 3 5 ....# ...#. ..... .#... #....
示例输出 1
3
我们可以将主教从 (1,3) to (3,5) 如下所示的三步,但不能为两步或更少步。
- (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)
示例输入 2
4 3 2 4 2 .... .... .... ....
示例输出 2
-1
没有办法将主教从 (3,2) to (4,2).
示例输入 3
18 18 1 1 18 .................. .####............. .#..#..####....... .####..#..#..####. .#..#..###...#.... .#..#..#..#..#.... .......####..#.... .............####. .................. .................. .####............. ....#..#..#....... .####..#..#..####. .#.....####..#.... .####.....#..####. ..........#..#..#. .............####. ..................
示例输出 3
9