P9322 [EGOI 2022] Superpiece / Super Piece

Day 2 Problem B. The statement is translated from [EGOI2022 superpiece](https://stats.egoi.org/media/task_description/2022_superpiece_en.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/)

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.

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.

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$.

**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