Problem Background

Day 2 Problem B.

This problem is translated from EGOI2022 superpiece.

Problem Description

You have an infinite chessboard. In this problem, the chessboard is an infinite two-dimensional grid, where each cell is represented by $(r, c)$, denoting the row and column respectively. Currently, there is a single piece on the board called the Superpiece. You have a list of legal moves for your Superpiece, which is a non-empty string that is a subset of QRBNKP. In each turn, the Superpiece can move as one of the given pieces. The Superpiece starts at position $(a, b)$ and you need to find the minimum number of moves to reach position $(c, d)$.

The following chess rules are used in this problem:

There are six types of pieces: Queen, Rook, Bishop, Knight, King, and Pawn. Their movement patterns are as follows:

• Queen (Q) can move to any cell in the same row, column, or diagonal. Formally, for any integer $k \ne 0$, the Queen can move from $(a, b)$ to $(a+k, b), (a, b+k), (a+k, b+k), (a+k, b-k)$.

• Rook (R) can move to any cell in the same row or column. Formally, for any integer $k \ne 0$, the Rook can move from $(a, b)$ to $(a+k, b), (a, b+k)$.

• Bishop (B) can move to any cell in the same diagonal. Formally, for any integer $k \ne 0$, the Bishop can move from $(a, b)$ to $(a+k, b+k), (a+k, b-k)$.

• Knight (N) moves in an "L" shape: two cells in one direction and then one cell in a perpendicular direction. Formally, the Knight can move from $(a, b)$ to $(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)$.

• King (K) can move to any of the eight adjacent cells. Formally, the King can move from $(a, b)$ to $(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)$.

• Pawn (P) can move one cell forward. Formally, the Pawn can move from $(a, b)$ to $(a+1, b)$.

Note that other chess rules you might know do not apply to this problem; only the rules listed above are used.

Input Format

The first line contains an integer $q$, the number of test cases. Each test case is described by two lines:

• The first line of each test case is a non-empty string, the list of legal moves for the Superpiece. This string is a subset of QRBNKP, appearing in the same order. In other words, it is a subsequence of QRBNKP.
• The second line of each test case contains four integers $a, b, c, d$ — the initial and target positions of the Superpiece. It is guaranteed that $(a, b) \ne (c, d)$, meaning the initial and target positions are different.

Output Format

For each test case, output a single line containing an integer $m$, the minimum number of moves required. If it is impossible to reach the target position, output $-1$.

Sample Input and Output

Sample Input #1

2
NKP
3 3 5 1
NKP
2 6 5 3

Sample Output #1

2
2

Sample Input #2

2
B
2 8 3 6
B
2 8 5 5

Sample Output #2

-1
1

Sample Input #3

2
Q
3 3 4 5
QR
4 1 1 4

Sample Output #3

2
1

Notes

Sample 1 Explanation

In the first set of data, we need to move from $(3,3)$ to $(5,1)$ with legal moves being Knight, King, and Pawn. There are multiple ways to achieve this in two moves, for example:

• Move Pawn to $(4,3)$, then Knight to $(5,1)$.
• Move Knight to $(5,2)$, then King to $(5,1)$.
• Move King to $(4,2)$, then King to $(5,1)$.

No fewer than two moves are possible — we need a Bishop or Queen to achieve that.

In the second set of data, we need to move from $(2,6)$ to $(5,3)$. Again, the optimal solution requires two moves. Each move must be a Knight, using $(4,5)$ or $(3,4)$ as intermediate steps.

Sample 2 Explanation

In the first set of data, we need to move from $(2,8)$ to $(3,6)$. Only Bishop moves are allowed, which is impossible.

In the second set of data, we need to move from $(2,8)$ to $(5,5)$ with only Bishop moves. This can be achieved in two moves, for example, using $(4,4)$ as an intermediate step.

Sample 3 Explanation

In the first set of data, we need to move from $(3,3)$ to $(4,5)$ with only Queen moves. This can be achieved in two moves using $(4,4)$ as an intermediate step.

In the second set of data, we need to move from $(4,1)$ to $(1,4)$ with only Queen and Rook moves. This can be achieved in one move.

Data Range

For all data, $1 \le q \le 10^3$, $-10^8 \le a, b, c, d \le 10^8$.

• Subtask 1 (12 points): Guaranteed to have Q, guaranteed not to have N.
• Subtask 2 (9 points): Guaranteed to have QN.
• Subtask 3 (13 points): Guaranteed to have R, guaranteed not to have Q.
• Subtask 4 (8 points): Guaranteed to have only B.
• Subtask 5 (6 points): Guaranteed to have B, guaranteed not to have QR.
• Subtask 6 (31 points): Guaranteed to have only N.
• Subtask 7 (8 points): Guaranteed to have N, guaranteed not to have QRB.
• Subtask 8 (7 points): Guaranteed to have K, guaranteed not to have QRBN.
• Subtask 9 (6 points): Guaranteed to have only P.

Note that the subtasks are not ordered by difficulty.

见题面 Input 部分

见题面 Output 部分