Description

Seeking a new challenge beyond Go, Fujiwara no Sai has recently discovered Chess.

He believes that the fastest way to master any board game is to grasp its ultimate goal—which, in Chess, is the "Checkmate." To sharpen his offensive skills, Sai is analyzing various historical chess puzzles. He wants to know if it is possible to break through the enemy lines and capture the opponent's King in 2 moves or fewer.

The chessboard is a standard 8x8 grid, with columns labeled A to H and rows labeled 1 to 8. Sai can use the following pieces, each following standard chess movement rules:

• Q (Queen): Moves any number of squares horizontally, vertically, or diagonally.

• R (Rook): Moves any number of squares horizontally or vertically.

• N (Knight): Moves in an "L" shape (two squares in one direction, then one square perpendicular). Only Knights can jump over other pieces.

• B (Bishop): Moves any number of squares diagonally.​

​​

Since Sai is practicing with static puzzles, the rules for this challenge are slightly modified:

1. Static Opponent: The opponent's pieces do not move; they simply act as obstacles.

2. Consecutive Moves: Sai can make up to 2 consecutive moves with his pieces to hunt down the King.

(Note: For simplicity, the movement of the player's Pawns (P) and King (K) is not considered. However, they may still be present on the board and act as obstacles. Furthermore, it is guaranteed that the opponent has exactly one piece: the King.)

You can use this code as a reference template.

#include <stdio.h>

typedef struct Position {
    int x;
    int y;
} Position;

typedef struct Piece {
    char type;
    Position pos;
} Piece;

typedef struct Move {
    Position start;
    Position end;
} Move;

typedef struct GameState {
    int player_count;
    Piece player[16];
    int opponent_count;
    Piece opponent[16];
    Move moves[2];
} GameState;

typedef struct SearchResult {
    int min_steps_to_checkmate;
    Move moves[2];
} SearchResult;

// If you would like to solve with BFS
// typedef struct QueueNode {
//     GameState state;
//     int step;
// } QueueNode;

const int QUEEN_DIRS[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
const int ROOK_DIRS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int KNIGHT_DIRS[8][2] = {{-1, 2}, {1, 2}, {-1, -2}, {1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
const int BISHOP_DIRS[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

void Check_Checkmate(...) {
    ...
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char type, pos_x, pos_y;
        GameState state;
        SearchResult result;
        result.min_steps_to_checkmate = 3;  // 3 indicates it is impossible to capture the King within two steps

        scanf("%d", &state.player_count);
        for (int i = 0; i < state.player_count; i++) {
            scanf(" %c %c%c", &type, &pos_x, &pos_y);
            state.player[i].type = type;
            state.player[i].pos.x = pos_x - 'A';
            state.player[i].pos.y = pos_y - '1';
        }

        scanf("%d", &state.opponent_count);
        for (int i = 0; i < state.opponent_count; i++) {
            scanf(" %c %c%c", &type, &pos_x, &pos_y);
            state.opponent[i].type = type;
            state.opponent[i].pos.x = pos_x - 'A';
            state.opponent[i].pos.y = pos_y - '1';
        }

        Check_Checkmate(...);

        if (result.min_steps_to_checkmate == 3) {
            printf("None\n");
        }
        else {
            printf("%d\n", result.min_steps_to_checkmate);
            for (int i = 0; i < result.min_steps_to_checkmate; i++) {
                printf("%c%c %c%c\n",
                       result.moves[i].start.x + 'A', result.moves[i].start.y + '1',
                       result.moves[i].end.x + 'A', result.moves[i].end.y + '1');
            }
        }
    }
}

Input

The first line contains an integer t, representing the number of test cases. For each test case:

• The first line contains an integer p, representing the number of Sai's (the player's) pieces.

• The next p lines describe Sai's pieces. Each line contains a character representing the piece type (Q, R, N...) and its position (e.g., A1), separated by a space.

• The next line contains an integer o, representing the number of the opponent's pieces.

• The following o lines describe the opponent's pieces in the same format.

Constraints:

• 1 <= t <= 1000000

• 1 <= p <= 16

• o = 1

Testcase Design:

• Testcase 1: Queen

• Testcase 2: Rook

• Testcase 3: Knight

• Testcase 4: Bishop

• Testcase 5~8: Unlimited

Output

For each test case:

• If the opponent's King can be captured in 2 moves or fewer, print the minimum number of moves n on the first line.

• For the next n lines, print the starting and ending positions of each move, separated by a space (e.g., A1 C3).

• If the King cannot be captured within 2 moves, print None on a single line.

• It is guaranteed that the optimal solution is strictly unique. That is, there is exactly one sequence of moves to achieve checkmate in the minimum number of steps.

Sample Input  Download

Sample Output  Download

Tags

Discuss