Background

Day 2 Problem B.

The statement is translated from EGOI2022 superpiece。

Problem Description

You have an infinite chessboard. In this problem, the board is an infinite 2D grid, and each square is denoted by $(r,c)$, representing the row and the column. There is currently exactly one piece on the board, called the superpiece. You are given the list of legal moves of your superpiece as a non-empty string, which is a subsequence of QRBNKP. In each turn, the superpiece may move as one of the given chess pieces. The superpiece starts at $(a,b)$. Find the minimum number of moves needed to reach $(c,d)$.

The chess rules that may be used in this problem are as follows:

There are six kinds of pieces: queen, rook, bishop, knight, king, and pawn. Their moves are:

• Queen (Q) can move to any square in the same row, the same column, or the same 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 square in the same row or the same 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 square on 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: first move two squares in one direction, then one square 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 squares. 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 square upward. Formally, the pawn can move from $(a,b)$ to $(a+1,b)$.

Note that other chess rules you may know do not apply to this problem; only use the rules listed above.

Input Format

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

• The first line of each test case contains a non-empty string, the legal move list of the superpiece. This string is a subset of QRBNKP, and all characters appear 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 starting and target positions of the superpiece. It is guaranteed that $(a,b)\ne (c,d)$, i.e., the start and target positions are different.

Output Format

For each test case, output one integer $m$ per line, the minimum number of moves. If it is impossible to reach the target position, output $-1$.

2
NKP
3 3 5 1
NKP
2 6 5 3

2
2

2
B
2 8 3 6
B
2 8 5 5

-1
1

2
Q
3 3 4 5
QR
4 1 1 4

2
1

Hint

Explanation for Sample $1$

In the first test case, we need to move from $(3,3)$ to $(5,1)$. The legal moves are knight, king, and pawn. There are many ways that take two moves, for example:

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

There is no solution with fewer than two moves—we would need a bishop or a queen to do that.

In the second test case, we need to move from $(2,6)$ to $(5,3)$. Similarly, the optimal solution takes two moves. Here, every move must be a knight move, using $(4,5)$ or $(3,4)$ as an intermediate square.

Explanation for Sample $2$

In the first test case, we need to move from $(2,8)$ to $(3,6)$. The piece can only move like a bishop, which is impossible.

In the second test case, we need to move from $(2,8)$ to $(5,5)$. The piece can only move like a bishop. It can be done in two moves, for example by using $(4,4)$ as an intermediate square.

Explanation for Sample $3$

In the first test case, we need to move from $(3,3)$ to $(4,5)$. The piece can only move like a queen. We can use $(4,4)$ as an intermediate square and reach it in two moves.

In the second test case, we need to move from $(4,1)$ to $(1,4)$. The piece can only move like a queen and a rook. It can be reached in one move.

Constraints

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

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

Note that the subtasks are not ordered by difficulty.

Translated by ChatGPT 5