UVa 11210 Chinese Mahjong (暴力,递归寻找)

题意:这个题意。有点麻烦,就是说给定13张牌,让你求能“听”的牌。(具体的见原题)

原题链接: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2151

析:看到这个题,真是麻烦啊,我又不懂麻将,看了好久才明白什么是“听”。分析一下思路。

首先对所有的牌都进行编号,然后暴力,首先的是先判断是哪个是将,然后再进一步判断,

哪一个是刻子,和顺子,用递归很简单的,只要全搜一下就好。整体不难,容易理解。

注意的是有的牌已经四张了,就不能再“听”了,这是一个坑。

代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std;
const int maxn = 15 + 5;
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[35], id[15];
char s[100]; int getid(const char *s){//获得每张牌的id
for(int i = 0; i < 34; ++i)
if(!strcmp(mahjong[i], s)) return i; return -1;
} bool dfs(int d){
for(int i = 0; i < 34; ++i) if(c[i] > 2){//刻子
if(3 == d) return true;//除了将,那么刻子和顺子的和应该是4个,所以这就已经判断安然无恙了
c[i] -= 3;
if(dfs(d+1)){ c[i] += 3; return true; }//找到时,要注意把c[i]改回来
c[i] += 3;
} for(int i = 0; i < 24; ++i)
if(i % 9 <= 6 && c[i] > 0 && c[i+1] > 0 && c[i+2] > 0) {//顺子
if(3 == d) return true;//同上
--c[i]; --c[i+1]; --c[i+2];
if(dfs(d+1)){ ++c[i]; ++c[i+1]; ++c[i+2]; return true; }//同上
++c[i]; ++c[i+1]; ++c[i+2];
} return false;
} bool judge(){
for(int i = 0; i < 34; ++i) if(c[i] > 1){//暴力,一张一张判断的,是不是将
c[i] -= 2;//判断是将了
if(dfs(0)){ c[i] += 2; return true; }//成立,要把c[i]改回来
c[i] += 2;
} return false;//不成立
} int main(){
// freopen("in.txt", "r", stdin);
int kase = 0;
bool ok;
while(scanf("%s", s) == 1){
if('0' == s[0]) break;
id[0] = getid(s);
for(int i = 1; i < 13; ++i){
scanf("%s", s);
id[i] = getid(s);//获得id
// printf("%d %d\n", i, id[i]);
}
// printf("\n");
ok = false; memset(c, 0, sizeof(c));//每次要清空
for(int i = 0; i < 13; ++i) ++c[id[i]];//获得每张牌的数量 // puts("++");
printf("Case %d:", ++kase);
for(int i = 0; i < 34; ++i){
if(c[i] > 3) continue;//如果这张牌已经四张了,就不能再听了,是坑 ++c[i];
if(judge()){
ok = true;
printf(" %s", mahjong[i]);//输出
}
--c[i];
} if(!ok) printf(" Not ready");
printf("\n");
}
return 0;
}
上一篇:微信web页面返回刷新


下一篇:FZU 2107 Hua Rong Dao(暴力回溯)