UVA 11210 Chinese Mahjong：麻將聽牌判斷的暴力回溯解法

題目大意

給定 13 張麻將牌（共 34 種，每種 4 張），判斷再摸哪一張牌可胡牌。胡牌定義：手牌可分為 1 個對子（眼）+ 4 個面子（刻子/順子）。不考慮特殊牌型（如七對、十三幺）。

核心思路：枚舉摸牌 + 回溯驗證

1. 將 34 種牌映射為 0~33：
   0~8: 1T~9T, 9~17: 1S~9S, 18~26: 1W~9W, 27:東, 28:南, 29:西, 30:北, 31:中, 32:發, 33:白。
2. 統計現有 13 張牌的計數 cnt[34]。
3. 枚舉 34 種牌作為摸牌：若 cnt[i] == 4 跳過；否則 cnt[i]++ 驗證能否胡牌。
4. 驗證函數 check()：
   • 枚舉眼的位置 i（cnt[i] >= 2），扣除 2 張。
   • 遞歸 dfs(depth) 處理剩余 12 張牌：優先嘗試刻子（cnt[i] >= 3），再嘗試順子（僅數字牌且 i%9 <= 6）。
   • 若 depth == 4 成功返回 true。
5. 收集所有聽牌，按題目順序輸出；無則輸出 Not ready。

C++ 代碼

#include 
using namespace std;
const vector tile = {
    "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"
};
int cnt[34], hand[13];

bool dfs(int formed) {
    if (formed == 4) return true;
    for (int i = 0; i < 34; ++i) {
        if (cnt[i] >= 3) { // 刻子
            cnt[i] -= 3;
            if (dfs(formed + 1)) return true;
            cnt[i] += 3;
        }
    }
    for (int i = 0; i <= 24; ++i) { // 順子（僅數字牌）
        if (i % 9 <= 6 && cnt[i] && cnt[i+1] && cnt[i+2]) {
            cnt[i]--; cnt[i+1]--; cnt[i+2]--;
            if (dfs(formed + 1)) return true;
            cnt[i]++; cnt[i+1]++; cnt[i+2]++;
        }
    }
    return false;
}

bool canWin() {
    for (int i = 0; i < 34; ++i) if (cnt[i] >= 2) {
        cnt[i] -= 2;
        if (dfs(0)) { cnt[i] += 2; return true; }
        cnt[i] += 2;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; int tc = 1;
    while (cin >> s, s != "0") {
        hand[0] = find(tile.begin(), tile.end(), s) - tile.begin();
        for (int i = 1; i < 13; ++i) {
            cin >> s;
            hand[i] = find(tile.begin(), tile.end(), s) - tile.begin();
        }
        cout << "Case " << tc++ << ":";
        bool any = false;
        for (int i = 0; i < 34; ++i) {
            fill(cnt, cnt+34, 0);
            for (int h : hand) ++cnt[h];
            if (cnt[i] == 4) continue;
            ++cnt[i];
            if (canWin()) {
                cout << ' ' << tile[i];
                any = true;
            }
        }
        if (!any) cout << " Not ready";
        cout << '\n';
    }
    return 0;
}

優化提示

• 狀態空間極小（34 種牌，每種 ≤4），暴力回溯極快。
• 可加記憶化（將 cnt 壓縮為 64 位整數）進一步加速，但非必要。
• 順子判斷利用 i%9 區分花色，避免跨花色順子。

總結

本題是「狀態空間小、規則固定」類問題的典型：枚舉決策點 + 回溯驗證。麻將胡牌判斷邏輯可抽象為「多重集合劃分為固定模式」，同樣適用於日本麻將、撲克牌型判斷等場景。