Description

The previous chess challenge was too difficult for Sai.

To build up his confidence and solidify his basic offensive skills, Sai has decided to try simpler challenge. He wants to know if it is possible to break through the enemy lines and capture the opponent's King in 3 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:

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

• P (Pawn): Moves straight forward one vacant square, but captures diagonally one square forward. (Note: To keep things simple, pawns cannot make an initial two-square move, and pawn promotion is ignored in this challenge.)

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 3 consecutive moves with his pieces to hunt down the King.

(Note: For simplicity, only the movement of the player's Rooks (R), Knight (N), and Pawn (P) is considered. However, other pieces may still be present on the board and act as obstacles. Furthermore, unlike the previous assignment, the opponent's army consists of more pieces than just the King. You must take into account situations where pieces block your path or can be captured.)

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[3];
} GameState;

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

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

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}};

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

int main() {
    char type, pos_x, pos_y;
    GameState state;
    SearchResult result;
    result.min_steps_to_checkmate = 4;  // 4 indicates it is impossible to capture the King within three 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 == 4) {
        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

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 <= p <= 16

• 1 <= o <= 16

Testcase Design:

• Testcase 1: o = 1, Rook

• Testcase 2: o = 1, Knight 

• Testcase 3: o = 1, Pawn

• Testcase 4: o = 1, Rook, Knight, Pawn

• Testcase 5~8: Unlimited

Output

For each test case:

• If the opponent's King can be captured in 3 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 3 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