102464: [AtCoder]ABC246 E - Bishop 2
Description
Score : $500$ points
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
Input
题意翻译
给定有障碍的网格图，`.` 为空地，`#` 为障碍。给定起点终点，每次移动仅可以斜向走任意长度，问从起点到终点的最少移动次数，可能无解，无解输出 `-1`。Output
.，格子$(i, j)$为空。
- 如果$S_{i,j}=$#，格子$(i, j)$被一个白色的兵占领，它不能移动或移除。
我们在格子$(A_x, A_y)$上放置了一个白色的象。
根据国际象棋的规则（见注释），找出将这个象从$(A_x, A_y)$移动到$(B_x, B_y)$所需的最少移动次数。如果无法移动到$(B_x, B_y)$，则报告-1。
注释
一个在$(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)$不被白色的兵占领。
约束
- $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
....#
...#.
.....