题解：UVA11210 Chinese Mahjong

· · 题解

UVA 11210 Chinese Mahjong 题解

题目传送门：

翻译题目

由于太长了所以懒得发工单翻译了。

本题考虑如下的五种牌型： 

格式：“类型：代号”
筒：1T~9T
条：1S~9S
万：1W~9W
风牌：DONG、NAN、XI、BEI
箭牌：ZHONG、FA、BAI

共 34 种牌，每种牌 4 张。

一组将牌：指的是两张相同的牌。
一组刻子：指的是三张相同的牌。 一组顺子：指的是三张相同牌型的牌（仅限筒条万），且它们的数字连续。

一组胡牌指的是满足含有一组将牌、四组面子的 14 张牌。其中一组面子可以是一组刻子或一组顺子。

现在给定 13 张牌，让你输出所有可能的第 14 张牌，使得它们能构成胡牌。如果有多个解，按顺序输出：1T~9T -> 1S~9S -> 1W~9W -> DONG -> NAN -> XI -> BEI -> ZHONG -> FA -> BAI。

思路

首先直接用牌的代号去管理牌肯定是不行的，所以考虑将每张牌都设置一个编码。编码的顺序就按上面那个顺序来。

然后，牌只有 14 张，数据量极小，于是考虑直接枚举第 14 张牌。开一个数组记录已经用的牌，然后确定第 14 张牌的可能取法。

检查是否能构成胡牌：首先先假设一组将牌，然后直接 DFS。DFS 中对于筒条万尝试所有可能的刻子和顺子，而风牌和箭牌则只尝试刻子即可。

Code

#include <bits/stdc++.h>
using namespace std;

/*
1T~9T 1~9
1S~9S 10~18
1W~9W 19~27
DONG 28
NAN 29
XI 30
BEI 31
ZHONG 32
FA 33
BAI 34
*/

int stoc(string code) {
    if (code == "DONG")
        return 28;
    else if (code == "NAN")
        return 29;
    else if (code == "XI")
        return 30;
    else if (code == "BEI")
        return 31;
    else if (code == "ZHONG")
        return 32;
    else if (code == "FA")
        return 33;
    else if (code == "BAI")
        return 34;
    else if (code[1] == 'T')
        return code[0] - '0';
    else if (code[1] == 'S')
        return code[0] - '0' + 9;
    else if (code[1] == 'W')
        return code[0] - '0' + 18;
}

int hand[15];
int use[35];
/*
bucket[] usage:
1: T
2: S
3: W
4: DONG
5: NAN
6: XI
7: BEI
8: ZHONG
9: FA
10: BAI
*/

string ctos[35] = {"", "1T", "2T", "3T", "4T", "5T", "6T", "7T", "8T", "9T", "1S", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "1W", "2W", "3W", "4W", "5W", "6W", "7W", "8W", "9W", "DONG", "NAN", "XI", "BEI", "ZHONG", "FA", "BAI"};

bool ok = false;
int cnt[35];

void dfs(int _3) {
    if (_3 >= 4) {
        ok = true;
        return;
    }
    if (ok)
        return;
    for (int i = 1; i <= 7; i++) {
        if (cnt[i] && cnt[i + 1] && cnt[i + 2]) {
            cnt[i]--;
            cnt[i + 1]--;
            cnt[i + 2]--;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i]++;
            cnt[i + 1]++;
            cnt[i + 2]++;
        }
        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i] += 3;
        }
    }
    for (int i = 8; i <= 9; i++)
        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i] += 3;
        }
    for (int i = 10; i <= 16; i++) {
        if (cnt[i] && cnt[i + 1] && cnt[i + 2]) {
            cnt[i]--;
            cnt[i + 1]--;
            cnt[i + 2]--;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i]++;
            cnt[i + 1]++;
            cnt[i + 2]++;
        }
        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i] += 3;
        }
    }
    for (int i = 17; i <= 18; i++)
        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i] += 3;
        }
    for (int i = 19; i <= 25; i++) {
        if (cnt[i] && cnt[i + 1] && cnt[i + 2]) {
            cnt[i]--;
            cnt[i + 1]--;
            cnt[i + 2]--;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i]++;
            cnt[i + 1]++;
            cnt[i + 2]++;
        }
        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i] += 3;
        }
    }
    for (int i = 26; i <= 27; i++)
        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i] += 3;
        }
    for (int i = 28; i <= 34; i++)
        if (cnt[i] >= 3) {
            cnt[i] -= 3;
            dfs(_3 + 1);
            if (ok)
                return;
            cnt[i] += 3;
        }
}

bool check() {
    memset(cnt, 0, sizeof(cnt));
    ok = false;
    for (int i = 1; i <= 14; i++)
        cnt[hand[i]]++;
    for (int i = 1; i <= 34; i++)
        if (cnt[i] >= 2) {
            ok = false;
            cnt[i] -= 2;
            dfs(0);
            if (ok)
                return true;
            cnt[i] += 2;
        }
    return false;
}

int main() {
    ios :: sync_with_stdio(false);
    int Ca = 0;
    while (true) {
        memset(hand, 0, sizeof(hand));
        Ca++;
        string mj;
        for (int i = 1; i <= 34; i++)
            use[i] = 4;
        for (int i = 1; i <= 13; i++) {
            cin >> mj;
            if (mj == "0")
                return 0;
            use[stoc(mj)]--;
            hand[i] = stoc(mj);
        }
        cout << "Case " << Ca << ": ";
        bool flag = false;
        for (int i = 1; i <= 34; i++) {
            if (use[i]) {
                hand[14] = i;
                if (check()) {
                    cout << ctos[i] << " ";
                    flag = true;
                }
            }
        }
        if (!flag)
            cout << "Not ready\n";
        else
            cout << "\n";
    }
    return 0;
}