Chinese Mahjong UVA - 11210 (暴力+回溯递归)

思路:得到输入得到mj[]的各个牌的数量,还差最后一张牌。直接暴力枚举34张牌就可以了。

   当假设得到最后一张牌,则得到了的牌看看是不是可以胡,如果可以胡的话,就假设正确。否者假设下一张牌。

   关键还是如何判断这组牌是不是可以胡。怎么判断呢?因为胡牌的条件是:nABC+mBBB+1DD, 而且n+m=4,其中n,m可以为0.

   下面是一张:递归DD的牌的递归情况:   

Chinese Mahjong UVA - 11210 (暴力+回溯递归)

然后:依次是找顺子和刻子也是相同的算法

#include<iostream>
#include<cstring>
using namespace std;
const char* mahjong[] = {
"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 c[], caseno, mj[];
char s[];
bool ok;
int consert(char *s){
for (int i = ; i < ;++i)
if (strcmp(mahjong[i], s) == )return i;
return -;
} bool Search(int dep){
for (int i = ; i < ; ++i) //判断顺子
if (c[i] >= ){
if (dep == )return true;
c[i] -= ;
if (Search(dep + ))return true;
c[i] += ;
}
for (int i = ; i < ;++i)
if (i % <= && c[i] >= && c[i + ] >= && c[i + ] >= ){
if (dep == )return true;
--c[i]; --c[i + ]; --c[i + ];
if (Search(dep + ))return true;
++c[i]; ++c[i + ]; ++c[i + ];
}
return false;
} bool check(){
for (int i = ; i < ;++i)
if (c[i] >= ){
c[i] -= ;
if(Search())return true; //开始搜索顺子和刻子
c[i] += ;
}
return false;
} int main(){
while (cin >> s){
if (s[] == '')break; ok = false;
//输入---------------------------
mj[] = consert(s);
for (int i = ; i < ; ++i)
{
cin >> s;
mj[i] = consert(s);
}
cout << "Case " << ++caseno << ":";
//开始暴力
for (int i = ; i < ; ++i){
memset(c, , sizeof(c));
for (int j = ; j < ; ++j)
c[mj[j]]++;
if (c[i] == )continue; //如果最后一张牌已经用光
c[i]++;
if (check()){ //判断可不可以胡牌
ok = true;
cout << " " << mahjong[i];
}
}
if (!ok)cout << " Not ready";
cout << endl;
}
return ;
}
上一篇:linux下vim如何配置markdown插件


下一篇:堆的判断(codevs 2879)