← 返回题目列表

AtCoder · abc246_e

H. 主教 2

中文机器翻译题面 查看原题

分数: 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