← 返回题目列表

Codeforces · 1765/I

I. 无限国际象棋

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

黑王生活在一个棋盘上,棋盘上有无数列(文件)和 $$$8$$$ 行(等级)。这些列均使用整数(包括负数)进行编号。这些行的编号从 $$$1$$$ 到 $$$8$$$。

最初,黑王位于起始方格$$$(x_s, y_s)$$$,他需要到达某个目标方格$$$(x_t, y_t)$$$。不幸的是,棋盘上也有白子,它们威胁着黑王。经过谈判,白棋同意让黑王传到目标方格,但条件如下:

- 每回合,黑王按照移动规则走一步;
- 黑王不能移动到白棋占据的方格;
- 黑王不能移动到受到任何白棋攻击的方格。如果根据移动规则,白子可以一步到达该方格,则该方格受到攻击;
- 白色棋子永远不会移动。

帮助黑王找到在不违反条件的情况下到达目标方格所需的最少步数。黑王任何时候都不能离开棋盘。

黑王按照下面的移动规则移动。尽管白子永远不会移动,但它们一移动能到达的方格就被认为是受到攻击,所以黑王不能进入这些方格。

以下是移动规则。请注意,棋子(除了马)不能跳过其他棋子。

- 国王在水平、垂直或对角线上恰好移动一格。
- 车水平或垂直移动任意数量的空方格。
- 主教对角移动任意数量的空方格。
- 皇后可以水平、垂直或对角移动任意数量的空方格。
- 一名骑士移动到不在同一行列、纵队或对角线上的最近方格之一(这可以被认为是水平移动两个方格然后垂直移动一个方格,或者水平移动一个方格然后垂直移动两个方格 - 即以“L”模式)。骑士不会被其他棋子阻挡,他们可以简单地跳过它们。

棋盘上没有棋子。

国王和骑士分别可能的行动。虚线表示马可以跳过其他棋子。

后、象和车分别可能的走法。

输入

第一行包含两个整数 $$$x_s$$$ 和 $$$y_s$$$ ($$$1 \le x_s \le 10^8$$$; $$$1 \le y_s \le 8$$$) — 黑王的起始坐标。

第二行包含两个整数 $$$x_t$$$ 和 $$$y_t$$$ ($$$1 \le x_t \le 10^8$$$; $$$1 \le y_t \le 8$$$) — 黑王的目标方格的坐标。

第三行包含一个整数 $$$n$$$ ($$$0 \le n \le 2000$$$) — 棋盘上白子的数量。

接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含一个字符 $$$t_i$$$ 和两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i \le 10^8$$$; $$$1 \le y_i \le 8$$$) — 的类型和坐标第 $$$i$$$ 个白色块。棋子的类型由以下大写拉丁字母表示:

- K — 王
- Q — 皇后
- R — 车
- B — 主教
- N — 骑士

棋盘上可以有任意数量的上面列出的任何类型的白色棋子,例如 $$$3$$$ 白色国王或 $$$4$$$ 白色皇后。棋盘上没有棋子。

输入的附加约束:

- 没有一个方格被超过一个白色棋子占据;
- 黑王的起始方格与他想要到达的方格不同,并且这两个方格都没有被任何白棋占据或攻击。

输出

打印一个整数——黑王在不违反条件的情况下到达目标方格所需的最少移动次数,如果不可能,则打印$$$-1$$$。

示例

输入 #1

1 8
7 8
2
N 4 8
B 4 6

输出 #1

10

输入 #2

1 1
1 5
2
K 1 3
R 2 3

输出 #2

6

输入 #3

2 2
6 4
1
Q 4 3

输出 #3

-1

注意

下图演示了第二个示例的解决方案。这里,字母K、R、s和t分别代表白王、白车、起始方格和目标方格​​。粗体十字标记了受到白棋攻击的方格。粗体点表示黑王的最短路径。