uva 11210 Chinese Mahjong

点击打开链接uva 11210

思路：模拟
分析：
1 根据题目我们可以知道总共有34种牌，分别是（9张饼+9张条+9张万+东南西北+中发白）
2 题目明确说明“胡牌”的请况是“将+刻子(>=0)+顺子(>=0)”，那么我们知道最多有34总牌，那么我们只要去枚举每一种是否可以作为将，然后去判断剩下的是否满足刻子和顺子即可
3 注意题目明确说明如果输入的时候是4张一样的牌，那么这个牌是不可能听的。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 34;
const char majong[N][N] = {
"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 ma[N];//记录每一种牌的个数

//返回拍的编号
int init(char *s){
   for(int i = 0 ; i < 34 ; i++)
      if(!strcmp(majong[i] , s))
         return i;
}

//判断当前将是否满足胡牌
bool isOk2(int pos){
    //枚举刻子
    for(int i = 0 ;  i< 34 ; i++){
       if(ma[i] >= 3){
          if(pos == 3)//为什么是3退出呢，因为最多4个刻子或者顺子，那么这里由于ma[i]>=3占了一个那么dep=3加起来就是4个了，所以dep为3返回
             return true;
          ma[i] -= 3;
          if(isOk2(pos+1))//递归回来判断
             return true;
          ma[i] += 3;
       }
    }
    //枚举顺子(因为东南西北和中发白是不可能构成顺子的)
    for(int i = 0 ; i <= 24 ; i++){
       if(i%9 <= 6 && ma[i] >= 1 && ma[i+1] >= 1 && ma[i+2] >= 1){
         if(pos == 3)//为什么是3退出呢，因为最多4个顺子或者顺子，那么这里由于ma[i]>=3占了一个那么dep=3加起来就是4个了，所以dep为3返回
            return true;
         ma[i]--;
         ma[i+1]--;
         ma[i+2]--;
         if(isOk2(pos+1))//递归回来判断
            return true;
         ma[i]++;
         ma[i+1]++;
         ma[i+2]++;
       }  
    }
    return false;
}

//枚举选将的所有可能
bool isOk(){
    for(int i = 0 ; i < 34 ; i++){//枚举将牌
       if(ma[i] >= 2){
          ma[i] -= 2;
          if(isOk2(0))
             return true;
          ma[i] += 2;//回溯
       }
    }
    return false;
}

int main(){
    int Case = 1;
    int tmp[N];
    char ch[N];
    bool mark;
    while(scanf("%s" , ch)){
        if(ch[0] == '0')
          break;
        //读入
        tmp[0] = init(ch);
        for(int i = 1 ; i < 13 ; i++){
           scanf("%s" , ch);
           tmp[i] = init(ch);
        }
        mark = false;
        printf("Case %d:" , Case++);
        //暴力枚举34张牌可能的情况
        for(int i = 0 ; i < 34 ; i++){
           memset(ma , 0 , sizeof(ma));//每一次初始化为全0
           for(int j = 0 ; j < 13 ; j++)
              ma[tmp[j]]++;
           if(ma[i] == 4)//如果牌是四张那么是不可能听的
              continue;
           ma[i]++;//假设拥有这一张牌
           if(isOk()){
              mark = true; 
              printf(" %s" , majong[i]);
           }
        }
        if(!mark)//如果所有的牌都没有听
          printf(" Not ready");
        printf("\n");
    }
    return 0;
}