题意分析

这道题目模拟了经典的祖玛游戏规则。我们需要判断玩家是否能够通过有限次数的插入操作，将所有桌面上的球消除干净。如果可以，则输出最少需要多少次插入；否则输出"lose"。

关键点：

1. 初始状态下不会有3个或以上同色球相连
2. 每次可以插入一个手球到任意位置
3. 插入后会触发消除机制（连续3个或以上同色球会被消除）
4. 消除可能会引发连锁反应
5. 目标是清空桌面上的所有球

解题思路

这是一个典型的BFS（广度优先搜索）问题，因为：

1. 我们需要找到最少操作次数（最短路径）
2. 每个状态可以派生出多个新状态
3. 需要避免重复访问相同状态

具体实现：

1. 使用队列存储待处理的状态
2. 每个状态包含：当前桌面球序列、剩余手球、已用步数
3. 对于每个状态，尝试所有可能的插入位置和手球选择
4. 每次插入后执行消除操作
5. 使用哈希集合记录已访问状态，避免重复计算
6. 当桌面为空时返回当前步数

标程代码

#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>
using namespace std;

struct GameState {
    string table;  // 当前桌面球序列
    string hand;   // 剩余手球
    int steps;     // 已用步数
    GameState(string t, string h, int s) : table(t), hand(h), steps(s) {}
};

// 消除连续3个或以上同色球
string eliminateBalls(string s) {
    bool changed;
    do {
        changed = false;
        for (int i = 0; i < (int)s.size(); ) {
            int j = i;
            while (j < (int)s.size() && s[j] == s[i]) j++;
            if (j - i >= 3) {
                s.erase(i, j - i);
                changed = true;
                break;  // 重新开始检查
            } else {
                i = j;
            }
        }
    } while (changed);
    return s;
}

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int m, k;
        cin >> m >> k;
        string table, hand;
        cin >> table >> hand;

        queue<GameState> q;
        unordered_set<string> visited;
        
        q.push(GameState(table, hand, 0));
        visited.insert(table + "|" + hand);  // 用分隔符区分table和hand
        
        bool solved = false;
        while (!q.empty()) {
            GameState current = q.front();
            q.pop();
            
            // 成功条件：桌面为空
            if (current.table.empty()) {
                cout << current.steps << endl;
                solved = true;
                break;
            }
            
            // 尝试所有可能的插入位置和手球
            for (int pos = 0; pos <= (int)current.table.size(); pos++) {
                for (int ballIdx = 0; ballIdx < (int)current.hand.size(); ballIdx++) {
                    // 构造新状态
                    string newTable = current.table.substr(0, pos) 
                                   + current.hand[ballIdx] 
                                   + current.table.substr(pos);
                    string newHand = current.hand.substr(0, ballIdx) 
                                  + current.hand.substr(ballIdx + 1);
                    
                    // 执行消除
                    newTable = eliminateBalls(newTable);
                    
                    // 检查是否已访问
                    string stateKey = newTable + "|" + newHand;
                    if (visited.find(stateKey) == visited.end()) {
                        visited.insert(stateKey);
                        q.push(GameState(newTable, newHand, current.steps + 1));
                    }
                }
            }
        }
        
        if (!solved) {
            cout << "lose" << endl;
        }
    }
    return 0;
}

代码优化说明

1. 使用结构体GameState封装游戏状态，提高代码可读性
2. eliminateBalls函数优化了消除逻辑，使用更清晰的循环结构
3. 状态键使用"|"分隔table和hand，避免混淆
4. 添加了适当的类型转换，避免编译器警告
5. 变量命名更加语义化，便于理解

这个解法通过BFS保证了找到最少操作次数，同时使用哈希集合避免了重复计算，在给定约束条件下（m≤20，k≤5）能够高效运行。

时间复杂度：O((m+k)!/(m!k!))（最坏情况下需要遍历所有可能的球排列组合） 空间复杂度：O((m+k)!/(m!k!))（需要存储所有可能的状态）