题解 UVA11210 【Chinese Mahjong】

2019-10-08 13:09:32


我们半个机房已经中了Majsoul的毒了......

至少这道题不用去判什么“无役”

思路就是首先枚举听什么,然后从字牌往数牌推,并且枚举顺子,再弄一些奇奇怪怪的剪枝就好了

注意:

  1. 如果你手上有4张相同的牌,你不能再听这张牌
  2. 14张牌中有单张字牌一定和不了
  3. 14张牌中有单张组不成顺子的数牌也和不了
  4. 输出要按筒,索,万,东南西北,中發白的顺序输出(majsoul打多了就会按万,索,筒,东南西北,白發中的顺序输出)
  5. UVA输出答案时貌似每行行末不能多空格
    #include <bits/stdc++.h>
    using namespace std;
    int cnt[40];//1p~9p筒子 1s~9s索子 1m~9m万子 ESWN风牌 Chun中 Hatsu發 Haku白
    char input[8];
    const char name[][10] = {"DONG","NAN","XI","BEI","ZHONG","FA","BAI"},
           type[][10] = {"T","S","W"};//输出用
    void add(char *s)
    {
    if (isdigit(s[0])) //数牌
    {
        if (s[1] == 'W') ++cnt[s[0] - 30];//万
        else if (s[1] == 'T') ++cnt[s[0] - 48];//筒
        else ++cnt[s[0] - 39];//索
    }
    else
    {
        //四风
        if (s[0] == 'D') ++cnt[28]; 
        else if (s[0] == 'N') ++cnt[29];
        else if (s[0] == 'X') ++cnt[30];
        else if (s[0] == 'B')
        {
            if (s[1] == 'E') ++cnt[31];else ++cnt[34];//北和白
        }
        else if (s[0] == 'F') ++cnt[33];//發
        else ++cnt[32];//中
    }
    }
    //从字牌往前推
    bool dfs(int pos = 34,bool has_pair = 0) 
    {
    if (!pos) return has_pair;//有雀头才能和
    if (!cnt[pos]) return dfs(pos - 1,has_pair);//跳过这张牌
    if (pos > 27) //字牌
    {
        if (cnt[pos] == 2) //当对子
        {
            if (has_pair) return 0;else return dfs(pos - 1,1);
        }
        if (cnt[pos] == 3) return dfs(pos - 1,has_pair); //当刻子
        return 0; //单张或四张都和不了
    }
    if ((pos - 1) % 9 < 2) //数牌1/2
    {
        if (cnt[pos] == 2) //对子
        {
            if (!has_pair) return dfs(pos - 1,1);
            else return 0;
        }
        if (cnt[pos] == 3) return dfs(pos - 1,has_pair); //刻子
        return 0;
    }
    //数牌3~9
    if (cnt[pos] == 2 && !has_pair && dfs(pos - 1,1)) return 1; //当雀头能和 
    if (cnt[pos] == 3 && dfs(pos - 1,has_pair)) return 1; //当刻子能和
    int num = 0;
    while (cnt[pos] && cnt[pos - 1] && cnt[pos - 2]) //搜顺子
    {
        --cnt[pos];--cnt[pos - 1];--cnt[pos - 2];++num;
        if (cnt[pos] == 1 || (cnt[pos] == 2 && has_pair))
            continue;
        if (dfs(pos - 1,has_pair | (cnt[pos] == 2)))
        {
            cnt[pos] += num;cnt[pos - 1] += num;cnt[pos - 2] += num;//回溯(之后还要搜有没有听别的牌)
            return 1;
        }
    }
    cnt[pos] += num;cnt[pos - 1] += num;cnt[pos - 2] += num;//回溯(可能还能拆牌)
    return 0;
    }
    int main ()
    {
    int _ = 0;
    while (1)
    {
        ++_;memset(cnt,0,sizeof(cnt));//牌数清零
        scanf("%s",input);
        if (input[0] == '0') break;
        printf("Case %d:",_);
        add(input);
        for (int i = 1;i <= 12;i++) scanf("%s",input),add(input);
        bool tinpai = 0;
        for (int i = 1;i <= 34;i++)
        {
            if (cnt[i] == 4) continue;//不能听手上有4张这种牌的牌
            if (i <= 27) //数牌
            {
                if (!cnt[i - 1] && !cnt[i] && !cnt[i + 1]) continue;//单张的凑不成顺子的数牌不搜
                ++cnt[i];
                if (dfs()) 
                    tinpai = 1,
                    printf(" %d%s",(i - 1) % 9 + 1,type[(i - 1) / 9]);
                --cnt[i];
            }
            else
            {
                if (!cnt[i]) continue;//单张字牌和不了
                ++cnt[i];
                if (dfs()) tinpai = 1,printf(" %s",name[i - 28]);
                --cnt[i];
            }
        }
        if (!tinpai) printf(" Not ready");
        putchar('\n');
    }
    return 0;
    }
    //送两组测试数据
    //1S 1S 1S 2S 3S 4S 5S 6S 7S 8S 9S 9S 9S
    //DONG DONG DONG NAN NAN NAN XI XI XI BEI BEI BEI FA
    //第一组纯正九莲宝灯,听任意一种索子(有兴趣的可以自己拆牌)
    //第二组大四喜+字一色,单骑听發