题解

问题分析:

我们需要找到一个最小的棋子集合，使得移除这些棋子后，棋盘上剩下的棋子互不攻击。这是一个典型的最小顶点覆盖问题，可以转化为二分图的最大匹配问题或使用回溯法求解。由于棋盘尺寸和棋子数量较小（最多15个棋子），可以采用状态压缩或回溯法枚举所有可能的移除方案，检查是否满足条件。

算法选择:

生成所有可能的子集：对于n个棋子，共有2n种可能的子集（保留或移除）。 检查合法性：对于每个子集，检查剩下的棋子是否互不攻击。 记录最小值：在所有合法的子集中，记录移除棋子数最少的方案。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Position {
    int x, y;
    char piece;
};

int minRemovals = INT_MAX;

bool isAttacking(const Position& a, const Position& b) {
    if (a.piece == 'E' || b.piece == 'E') return false;
    
    int dx = abs(a.x - b.x);
    int dy = abs(a.y - b.y);
    
    // King attack
    if (a.piece == 'K' || b.piece == 'K') {
        if (dx <= 1 && dy <= 1) return true;
    }
    
    // Rook attack
    if (a.piece == 'R' || b.piece == 'R') {
        if (dx == 0 || dy == 0) return true;
    }
    
    // Bishop attack
    if (a.piece == 'B' || b.piece == 'B') {
        if (dx == dy) return true;
    }
    
    // Queen attack (combines rook and bishop)
    if (a.piece == 'Q' || b.piece == 'Q') {
        if (dx == 0 || dy == 0 || dx == dy) return true;
    }
    
    // Knight attack
    if (a.piece == 'N' || b.piece == 'N') {
        if ((dx == 1 && dy == 2) || (dx == 2 && dy == 1)) return true;
    }
    
    return false;
}

bool hasConflict(const vector<Position>& board) {
    for (size_t i = 0; i < board.size(); ++i) {
        if (board[i].piece == 'E') continue;
        for (size_t j = i+1; j < board.size(); ++j) {
            if (board[j].piece == 'E') continue;
            if (isAttacking(board[i], board[j])) {
                return true;
            }
        }
    }
    return false;
}

void backtrack(vector<Position>& board, int index, int removed) {
    if (!hasConflict(board)) {
        if (removed < minRemovals) {
            minRemovals = removed;
        }
        return;
    }
    
    if (index >= (int)board.size() || removed >= minRemovals) {
        return;
    }
    
    // Option 1: don't remove current piece
    backtrack(board, index+1, removed);
    
    // Option 2: remove current piece (if it's not empty)
    if (board[index].piece != 'E') {
        char original = board[index].piece;
        board[index].piece = 'E';
        backtrack(board, index+1, removed+1);
        board[index].piece = original;
    }
}

int main() {
    string line;
    while (cin >> line, line == "START") {
        int width, height;
        cin >> width >> height;
        
        vector<Position> board;
        for (int y = 0; y < height; ++y) {
            for (int x = 0; x < width; ++x) {
                char piece;
                cin >> piece;
                Position pos;
                pos.x = x;
                pos.y = y;
                pos.piece = piece;
                board.push_back(pos);
            }
        }
        
        cin >> line; // Read "END"
        
        minRemovals = INT_MAX;
        backtrack(board, 0, 0);
        
        cout << "Minimum Number of Pieces to be removed: " << minRemovals << endl;
    }
    return 0;
}

算法说明：

1. 数据结构：

   • 使用Position结构体存储每个棋子的位置和类型

2. 攻击判断：

   • isAttacking函数根据国际象棋规则判断两个棋子是否互相攻击
   • 分别处理各种棋子的攻击方式（国王、皇后、车、主教、骑士）

3. 冲突检测：

   • hasConflict函数检查当前棋盘是否存在互相攻击的棋子

4. 回溯算法：

   • 递归尝试移除或不移除每个棋子
   • 剪枝：当当前移除数已超过已知最小值时停止搜索
   • 保存最优解（最小移除数）

5. 输入输出：

   • 严格按照题目要求的格式处理输入
   • 输出最小需要移除的棋子数

复杂度分析：

• 时间复杂度：O(2^n)，其中n是棋子数量（最多15个）
• 空间复杂度：O(n)，用于存储棋盘状态