| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 6 | 2 | 2 | 66.667% |
You are given an infinite chessboard. In this task, a chessboard is an infinite two-dimensional grid of squares, where each square is indexed by a pair of integers (r, c), denoting the row and the column respectively. The only piece currently present on the chessboard is the superpiece. You are given a list of valid moves of your superpiece, which will be specified as a non-empty string containing a subset of the characters in "QRBNKP". In each turn, the superpiece can move as one of the given chess pieces. The superpiece is initially positioned at square (a, b). Calculate the minimum number of moves needed to reach the square (c, d).
The subset of the chess rules applicable for this problem are given below.
There are six types of pieces: queen, rook, bishop, knight, king and pawn. They move the following way:
Note that the other rules or moves that you might know about chess do not apply in this problem; please only use the ones listed above.
Also, note that while the symbol denoting the chess piece is often the first letter of its name in English, it is the second letter for the "kNight" (to avoid confusion with the "King").
The first line of the input contains an integer q, representing the number of queries your program will be tested on. Each two of the following lines describe a query:
For each of the q queries, output a single line containing an integer m representing the minimum number of moves the superpiece needs to reach the target from its original position for that query. If it is not possible to reach the target from the original position for a query, output −1 instead.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | No 'N' character and a guaranteed 'Q' character in the first line of each query. |
| 2 | 9 | Guaranteed 'Q' and 'N' characters (both) in the first line of each query. |
| 3 | 13 | No 'Q' character and a guaranteed 'R' character in the first line of each query. |
| 4 | 8 | The first line of each query is always "B". |
| 5 | 6 | No 'Q' or 'R' characters and a guaranteed 'B' character in the first line of each query. |
| 6 | 31 | The first line of each query is always "N". |
| 7 | 8 | No 'Q', 'R', or 'B' characters and a guaranteed 'N' character in the first line of each query. |
| 8 | 7 | No 'Q', 'R', 'B', or 'N' characters and a guaranteed 'K' character in the first line of each query. |
| 9 | 6 | The first line of each query is always "P". |
Note that subtasks are not ordered in the expected order of their difficulty.
2 NKP 3 3 5 1 NKP 2 6 5 3
2 2
In the first query, we are asked to go from (3, 3) to (5, 1), using the moves of knight, king and pawn. There are multiple ways of doing this in exactly 2 moves, for example:
There is no way of achieving this by fewer than two moves - we would need a bishop or a queen to do that.
In the second query, we are asked to go from (2, 6) to (5, 3). Again, the optimal solution is to use two moves. This time, both of these moves have to be knight moves, with the intermediate square being (4, 5) or (3, 4).
2 B 2 8 3 6 B 2 8 5 5
-1 1
In the first query, we are asked to go from (2, 8) to (3, 6). Provided only the bishop's moves, it is not possible to do this.
In the second query, we are asked to go from (2, 8) to (5, 5), again using only bishop's moves. It is possible to do this in one move.
2 Q 3 3 4 5 QR 4 1 1 4
2 1
In the first query, we are asked to go from (3, 3) to (4, 5) using the queen's moves. It is possible to do this in two moves, for instance, by using (4, 4) as an intermediate point.
In the second query, we are asked to go from (4, 1) to (1, 4), using the moves of queen and rook. It is possible to do this in one move.