Score : $500$ points

问题描述

我们有一个 $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。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have an $N \times N$ chessboard. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left of this board.
The board is described by $N$ strings $S_i$.
The $j$-th character of the string $S_i$, $S_{i,j}$, means the following.

• If $S_{i,j}=$ ., the square $(i, j)$ is empty.
• If $S_{i,j}=$ #, the square $(i, j)$ is occupied by a white pawn, which cannot be moved or removed.

We have put a white bishop on the square $(A_x, A_y)$.
Find the minimum number of moves needed to move this bishop from $(A_x, A_y)$ to $(B_x, B_y)$ according to the rules of chess (see Notes).
If it cannot be moved to $(B_x, B_y)$, report -1 instead.

Notes

A white bishop on the square $(i, j)$ can go to the following positions in one move.

• For each positive integer $d$, it can go to $(i+d,j+d)$ if all of the conditions are satisfied.

  • The square $(i+d,j+d)$ exists in the board.
  • For every positive integer $l \le d$, $(i+l,j+l)$ is not occupied by a white pawn.

• For each positive integer $d$, it can go to $(i+d,j-d)$ if all of the conditions are satisfied.

  • The square $(i+d,j-d)$ exists in the board.
  • For every positive integer $l \le d$, $(i+l,j-l)$ is not occupied by a white pawn.

• For each positive integer $d$, it can go to $(i-d,j+d)$ if all of the conditions are satisfied.

  • The square $(i-d,j+d)$ exists in the board.
  • For every positive integer $l \le d$, $(i-l,j+l)$ is not occupied by a white pawn.

• For each positive integer $d$, it can go to $(i-d,j-d)$ if all of the conditions are satisfied.

  • The square $(i-d,j-d)$ exists in the board.
  • For every positive integer $l \le d$, $(i-l,j-l)$ is not occupied by a white pawn.

Constraints

• $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$ is a string of length $N$ consisting of . and #.
• $S_{A_x,A_y}=$ .
• $S_{B_x,B_y}=$ .

Input

Input is given from Standard Input in the following format:

$N$

$A_x$ $A_y$

$B_x$ $B_y$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print the answer.

Sample Input 1

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

Sample Output 1

3

We can move the bishop from $(1,3)$ to $(3,5)$ in three moves as follows, but not in two or fewer moves.

• $(1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)$

Sample Input 2

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

Sample Output 2

-1

There is no way to move the bishop from $(3,2)$ to $(4,2)$.

Sample Input 3

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

Sample Output 3

9

update @ 2024/3/10 10:33:42