题解 UVA11210 【Chinese Mahjong】

我们半个机房已经中了[Majsoul](http://majsoul.com/1/)的毒了...... 至少这道题不用去判什么“无役” 思路就是首先枚举听什么，然后从字牌往数牌推，并且枚举顺子，再弄一些奇奇怪怪的剪枝就好了 注意： 1. 如果你手上有4张相同的牌，你不能再听这张牌 2. 14张牌中有单张字牌一定和不了 3. 14张牌中有单张组不成顺子的数牌也和不了 4. 输出要按筒，索，万，东南西北，中發白的顺序输出（majsoul打多了就会按万，索，筒，东南西北，白發中的顺序输出） 5. UVA输出答案时貌似每行行末不能多空格 ```cpp #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 //第一组纯正九莲宝灯，听任意一种索子（有兴趣的可以自己拆牌） //第二组大四喜+字一色，单骑听發 ```