黑王生活在一个棋盘上,棋盘上有无数列(文件)和 $$$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分别代表白王、白车、起始方格和目标方格。粗体十字标记了受到白棋攻击的方格。粗体点表示黑王的最短路径。