#4007. [ABC 246] E. Bishop 2

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Sky390

题目描述

英文原题面:https://atcoder.jp/contests/abc246/tasks/abc246_e

我们有一个 棋盘。 令 表示该棋盘顶部从第 -th 行和从左侧开始的第 -th 列的正方形。

棋盘由 个字符串 描述。

字符串 的第 个字符, 的含义如下:

  • 如果 = .,则正方形 为空。

  • 如果 = #,则 位置被一个白棋占据,不能被移动或移除。

我们在 的位置上放了一个白象。

根据国际象棋的规则(见注释),找出将此象从 移至 所需的最少步数。

如果它不能被移到 ,输出 -1 代替。

Notes

广场上的白色象 可以一次移动到以下位置:

  • 对于每个正整数 ,如果所有的条件都满足,它可以去到
    • 棋盘中存在 这个方格。
    • 对于每一个正整数 都没有被白棋占据。

  • 对于每个正整数 ,如果所有的条件都满足,它可以去
    • 棋盘中存在 这个方格。
    • 对于每一个正整数 都没有被白棋占据。

  • 对于每个正整数 ,如果所有的条件都满足,它可以去
    • 棋盘中存在 这个方格。
    • 对于每一个正整数 都没有被白棋占据。

  • 对于每个正整数 ,如果所有的条件都满足,它可以去
    • 棋盘中存在 这个方格。
    • 对于每个正整数 都没有被白棋占据。

输入格式

输入由以下格式的标准输入构成:

N
A_x A_y
B_x B_y
S_1
S_2
···
S_N

输出格式

输出答案。

样例

样例输入 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

样例输出 1

3

样例输入 2

4
3 2
4 2
....
....
....
....

样例输出 2

-1

样例输入 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

样例输出 3

9

数据范围与提示

约束条件

  • 是一个长度为 的字符串,由 .# 组成。
  • = .
  • = .

样例解释

样例 1 解释:我们可以按如下三步将象从 移动到 ,但不能用两步或更少的步数。

样例 2 解释:没有办法把象从 移动到