A5415 | Bishop 2
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
有一个 $N \times N$ 的国际象棋棋盘。棋盘上从上往下第 $i$ 行，从左往右第 $j$ 列的格子称为格子 $(i, j)$。
棋盘的信息以 $N$ 个字符串 $S_i$ 给出。
字符串 $S_i$ 的第 $j$ 个字符 $S_{i,j}$ 包含以下信息：
- 当 $S_{i,j} = \texttt{.}$ 时，格子 $(i, j)$ 上没有任何棋子。
- 当 $S_{i,j} = \texttt{\#}$ 时，格子 $(i, j)$ 上有一个白色兵（pawn）。这个兵不能被移动或移除。
现在在棋盘的格子 $(A_x, A_y)$ 上放置了一个白色主教（bishop）。
请你求出，按照国际象棋的规则（见下方注释），将这个主教从 $(A_x, A_y)$ 移动到 $(B_x, B_y)$ 所需的最少步数。
如果无法移动到目标位置，则输出 $-1$。
棋盘的信息以 $N$ 个字符串 $S_i$ 给出。
字符串 $S_i$ 的第 $j$ 个字符 $S_{i,j}$ 包含以下信息：
- 当 $S_{i,j} = \texttt{.}$ 时，格子 $(i, j)$ 上没有任何棋子。
- 当 $S_{i,j} = \texttt{\#}$ 时，格子 $(i, j)$ 上有一个白色兵（pawn）。这个兵不能被移动或移除。
现在在棋盘的格子 $(A_x, A_y)$ 上放置了一个白色主教（bishop）。
请你求出，按照国际象棋的规则（见下方注释），将这个主教从 $(A_x, A_y)$ 移动到 $(B_x, B_y)$ 所需的最少步数。
如果无法移动到目标位置，则输出 $-1$。
输入格式
输入以如下格式从标准输入读入：
第一行输入一个正整数 $N$
第二行输入两个整数${A_x , A_y}$
第三行输入两个整数${B_x , B_y}$
接下来$N$行，每行一个长度为$N$的字符串
第一行输入一个正整数 $N$
第二行输入两个整数${A_x , A_y}$
第三行输入两个整数${B_x , B_y}$
接下来$N$行，每行一个长度为$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
### 注释
放在格子 $(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) \ne (B_x, B_y)$
- $S_i$ 是由
- $S_{A_x, A_y} = \texttt{.}$
- $S_{B_x, B_y} = \texttt{.}$
### 样例解释 1
如下图所示，可以通过 $3$ 步将主教从 $(1, 3)$ 移动到 $(3, 5)$。无法在 $2$ 步以内完成。
- $(1, 3) \rightarrow (2, 2) \rightarrow (4, 4) \rightarrow (3, 5)$
### 样例解释 2
无论如何移动主教，都无法将其从 $(3, 2)$ 移动到 $(4, 2)$。
放在格子 $(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) \ne (B_x, B_y)$
- $S_i$ 是由
. 和 # 组成的长度为 $N$ 的字符串- $S_{A_x, A_y} = \texttt{.}$
- $S_{B_x, B_y} = \texttt{.}$
### 样例解释 1
如下图所示，可以通过 $3$ 步将主教从 $(1, 3)$ 移动到 $(3, 5)$。无法在 $2$ 步以内完成。
- $(1, 3) \rightarrow (2, 2) \rightarrow (4, 4) \rightarrow (3, 5)$
### 样例解释 2
无论如何移动主教，都无法将其从 $(3, 2)$ 移动到 $(4, 2)$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？