雀魂麻将

描述

现有一种雀魂麻将游戏，规则如下：

• 总共有36张牌，每张牌是1~9。每个数字4张牌。
• 你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌
  • 14张牌中有2张相同数字的牌，称为雀头。
  • 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234，567等），刻子的意思是相同数字的3个数字牌（例如111，777）

例如：
1 1 1 2 2 2 6 6 6 7 7 7 9 9 用9做雀头，组1，2，6，7的4个刻子，可以和牌
1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头，组123，123，567，789的四个顺子，可以和牌
1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。

假设你现在手中已经有13张牌，输出所有能和牌的最后一张牌的牌型，若没有则输出0

分析

因为牌型总共只有9种，所以完全可以直接枚举，判断9种情况下能否和牌。判断是否和牌首先需要选择合适的雀头，而雀头必须选择数量大于2的牌型，为方便处理，我们可以用一个长度为9的数组 来表示这14张牌（ 表示牌型 的数量）。枚举所有可能的雀头，判断剩下的12张牌能否组成4个刻子或是顺子。从头到尾遍历数组，找到第一个可能的刻子或是顺子，删去这3张牌，判断剩下的9张牌能否组成3个刻子或顺子。可以发现这是一个递归的过程，递归的出口就是牌被删光了（和牌）或是剩下的牌中找不到刻子或是顺子（不和牌）。一旦找到一种和牌的情况则可以直接结束递归寻找的过程，并将当前枚举的牌型加入结果数组中。但是需要注意的一个问题是需要将之前删去的牌复原，以至于不影响后续的枚举判断过程。

代码

#include <bits/stdc++.h>

using namespace std;

// 判断是否组成k对刻子或顺子
bool check2(int* a, int k) {
    if(k == 0) return true;
    int p = 0;
    while(p < 9 && a[p] == 0) p++;

    bool flag = false;
    if(a[p] >= 3) {
        a[p] -= 3;
        if(check2(a, k-1)) flag = true;
        a[p] += 3;
        if(flag) return true;
    }

    if(p <= 6 && a[p+1] >= 1 && a[p+2] >= 1) {
        a[p]--; a[p+1]--; a[p+2]--;
        if(check2(a, k-1)) flag = true;
        a[p]++; a[p+1]++; a[p+2]++;
        if(flag) return true;
    }

    return false;
}

bool check(int* a) {
    bool flag = false;
    // 选雀头
    for(int i = 0; i < 9; i++) {
        if(a[i] >= 2) {
            a[i] -= 2;
            if(check2(a, 4)) flag = true;  // 不能直接返回，因为需要复原数组
            a[i] += 2;
            if(flag) return true;
        }
    }

    return false;
}

int main() {
    int a[9] = {0};
    for(int i = 0; i < 13; i++) {
        int x; cin >> x;
        a[x-1]++;
    }

    int ans[9] = {0}; int k = 0;
    for(int i = 1; i <= 9; i++) {  // 枚举牌型 1~9
        if(a[i-1] == 4) continue;  // 牌型 i 已经全在手中

        a[i-1]++;
        if(check(a)) ans[k++] = i;
        a[i-1]--;
    }

    cout << ans[0];
    for(int i = 1; i < k; i++) {
        cout << " " << ans[i];
    }
}