题目描述

题目译自 European Girls' Olympiad in Informatics 2022 Day2 T2. Superpiece

想象你面前有一个无限大的棋盘。这个棋盘是一个无限的二维格子，每个格子用一对整数 $(r, c)$ 表示，分别代表行和列。现在棋盘上只有一枚超级棋子。你会收到一个描述这枚超级棋子移动规则的非空字符串，字符串由 QRBNKP 中的部分字符组成。每一步，这枚超级棋子都可以选择一种给定的棋子移动方式。棋子初始位于格子 $(a, b)$，你的任务是计算它到达格子 $(c, d)$ 所需的最少步数。

本题适用的棋类规则如下。这里有六种棋子：后 (Queen)、车 (Rook)、象 (Bishop)、马 (kNight)、王 (King) 和兵 (Pawn)，它们的移动方式分别是：

• 后 (Q)：可以移动到当前格子所在行、列或对角线上的任意格子。形式上，对于任意非零整数 $k$，后可以从 $(a, b)$ 移动到 $(a, b+k)$、$(a+k, b)$、$(a+k, b+k)$ 或 $(a+k, b-k)$。

• 车 (R)：可以移动到当前格子所在行或列上的任意格子。形式上，对于任意非零整数 $k$，车可以从 $(a, b)$ 移动到 $(a+k, b)$ 或 $(a, b+k)$。

• 象 (B)：可以移动到当前格子所在对角线上的任意格子。形式上，对于任意非零整数 $k$，象可以从 $(a, b)$ 移动到 $(a+k, b+k)$ 或 $(a+k, b-k)$。

• 马 (N)：以“L”形移动，先沿一个方向走两格，再向垂直方向走一格。形式上，马可以从 $(a, b)$ 移动到 $(a+1, b+2)$、$(a+1, b-2)$、$(a+2, b+1)$、$(a+2, b-1)$、$(a-2, b+1)$、$(a-2, b-1)$、$(a-1, b+2)$ 或 $(a-1, b-2)$。

• 王 (K)：可以移动到当前格子周围八个相邻格子中的任意一个。形式上，王可以从 $(a, b)$ 移动到 $(a, b+1)$、$(a, b-1)$、$(a+1, b)$、$(a-1, b)$、$(a+1, b+1)$、$(a+1, b-1)$、$(a-1, b+1)$ 或 $(a-1, b-1)$。

• 兵 (P)：只能向上移动一格。形式上，兵可以从 $(a, b)$ 移动到 $(a+1, b)$。

注意，本题只适用以上列出的规则，其他你可能知道的棋类规则在这里不适用。

另外，虽然棋子的符号通常是英文名称的首字母，但马（kNight）用的是第二个字母 N（以避免与王（King）混淆）。

输入格式

第一行包含一个整数 $q$，表示测试你的程序的请求数量。接下来的每两行描述一个请求：

• 请求的第一行是一个非空字符串，指定超级棋子可以使用的棋子移动方式。这个字符串是 QRBNKP 的子序列，包含的字符按原顺序排列。
• 请求的第二行包含四个空格分隔的整数 $a, b, c, d$，表示超级棋子的起始位置和目标位置。保证 $(a, b) \neq (c, d)$，即起始位置与目标位置不同。

输出格式

对于 $q$ 个请求中的每个，输出一行，包含一个整数 $m$，表示超级棋子从起始位置到达目标位置所需的最少步数。如果无法到达目标位置，输出 $-1$。

2
NKP
3 3 5 1
NKP
2 6 5 3

2
2

在第一个请求中，你需要从 $(3,3)$ 到 $(5,1)$，可用马、王和兵的移动方式。可以用正好 2 步完成，例如：

• 先以兵的方式移到 $(4,3)$，再以马的方式移到 $(5,1)$。
• 先以马的方式移到 $(5,2)$，再以王的方式移到 $(5,1)$。
• 先以王的方式移到 $(4,2)$，再以王的方式移到 $(5,1)$。

少于两步无法实现，需要象或后才能一步到位。

在第二个请求中，你需要从 $(2,6)$ 到 $(5,3)$。最优解也是两步，这次必须都用马的移动，中间点可以是 $(4,5)$ 或 $(3,4)$。

2
B
2 8 3 6
B
2 8 5 5

-1
1

在第一个请求中，你需要从 $(2,8)$ 到 $(3,6)$，只能用象的移动方式，无法实现。

在第二个请求中，你需要从 $(2,8)$ 到 $(5,5)$，也只能用象的移动方式。这次一步即可完成。

2
Q
3 3 4 5
QR
4 1 1 4

2
1

在第一个请求中，你需要从 $(3,3)$ 到 $(4,5)$，用后的移动方式。可以用两步完成，例如经过中间点 $(4,4)$。

在第二个请求中，你需要从 $(4,1)$ 到 $(1,4)$，可用后和车的移动方式。一步即可完成。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq q \leq 1000$
• 对于每个请求，$-10^{8} \leq a, b, c, d \leq 10^{8}$
• 棋盘在所有方向上都是无限大的

详细子任务附加限制及分值如下表所示。

注意，子任务的顺序并非按难度排列。