说明

该程序模拟了“手风琴”接龙纸牌游戏。游戏规则要求将牌从左到右排列，并根据特定规则移动牌堆，直到无法继续移动为止。程序读取输入的牌组，模拟游戏过程，并输出最终剩余的牌堆数量及各堆的牌数。

算法标签

• 模拟
• 栈操作
• 贪心算法

解题思路

1. 问题分析：游戏规则要求牌可以移动到左边第一张或第三张牌上，如果花色或点数相同。移动后需要填补空缺，直到无法移动为止。
2. 输入处理：读取多组牌组，每组52张牌，直到遇到#结束。
3. 游戏模拟：
   • 初始化牌堆，每张牌作为一个单独的堆。
   • 遍历牌堆，检查每张牌是否可以移动到左边第一张或第三张牌上，优先检查第三张。
   • 移动牌后，移除空堆并填补空缺。
4. 输出结果：输出最终剩余的牌堆数量及各堆的牌数。

分析

• 牌堆表示：使用vector<vector<Card>>表示牌堆，每个子vector代表一个牌堆。
• 移动规则：
  • 优先检查左边第三张牌（如果存在），再检查左边第一张牌。
  • 移动后，移除空堆并调整牌堆顺序。
• 终止条件：当没有牌可以移动时，游戏结束。

实现步骤

1. 初始化牌堆：将每张牌初始化为一个单独的堆。
2. 遍历牌堆：
   • 从右到左检查每张牌是否可以移动。
   • 优先检查左边第三张牌，再检查左边第一张牌。
   • 移动牌后，调整牌堆结构。
3. 输出结果：统计并输出剩余的牌堆数量及各堆的牌数。

代码解释

• 数据结构：
  • Card结构体：表示一张牌，存储牌的点数和花色。
  • eq函数：判断两张牌是否可以移动（花色或点数相同）。
• 输入处理：
  • 循环读取每组牌组，直到遇到#结束。
• 游戏模拟：
  • 初始化牌堆。
  • 遍历牌堆，检查移动条件并执行移动。
  • 移除空堆并填补空缺。
• 输出：格式化输出剩余的牌堆数量及各堆的牌数。

该程序通过精确的牌堆移动和结构调整，高效地模拟了“手风琴”接龙游戏，并正确输出了游戏结果。

代码

/* POJ1214 "Accordian" Patience */

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 52;
struct Card {
    char c[3];
};

bool eq(Card& a, Card& b)
{
    return a.c[0] == b.c[0] || a.c[1] == b.c[1];
}

int main()
{
    for(;;) {
        vector< vector<Card> > v;
        Card a;

        for(int i = 0; i < N; i++) {
            scanf("%s", a.c);
            if(a.c[0] == '#')
                return 0;

            vector<Card> s;
            s.push_back(a);
            v.push_back(s);

            for(int j = v.size()-1, k; j < (int)v.size(); j++) {
                Card c = v[j].back();
                for(k = j; k > 0; k--) {
                    if(k >= 3 && eq(c, v[k-3].back())) {
                        k = k - 2;
                        continue;
                    }
                    if(!eq(c, v[k-1].back()))
                        break;
                }
                if(k != j) {
                    v[k].push_back(v[j].back());
                    v[j].pop_back();
                    if(v[j].empty())
                        v.erase(v.begin() + j);
                }
                j = k;
            }
        }

        int len = v.size();
        printf("%d piles remaining:", len);
        for(int i = 0; i < len; i++)
            printf(" %d", v[i].size());
        printf("\n");
    }

    return 0;
}