首页 > 代码库 > UVA 11210 Chinese Mahjong

UVA 11210 Chinese Mahjong

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}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 id(char *s){        for (int i = 0 ; i < 34; i++)                if (strcmp(s,mahjong[i]) == 0) return i ;        return -1;}int cnt[34];bool found;void dfs(int cur){        if (found) return ;        if (cur == 0) {found = true; return ;}        for (int i = 0 ; i < 34;i ++)        {                if (cnt[i] >= 3)                {                        cnt[i] -= 3;                        dfs(cur - 3);                        if (found) return ;                        cnt[i] += 3;                }        }        for (int i = 0 ; i < 7; i++)        {                if (cnt[i] && cnt[i + 1] && cnt[i + 2])                {                        cnt[i]--;cnt[i + 1]--;cnt[i + 2]--;                        dfs(cur - 3);if (found) return ;                        cnt[i]++;cnt[i + 1]++;cnt[i +2]++;                }        }        for (int i = 9; i < 16; i++)        {                if (cnt[i] && cnt[i + 1] &&cnt[i + 2])                {                        cnt[i]--;cnt[i + 1]--;cnt[i + 2]--;                        dfs(cur - 3);if (found) return ;                        cnt[i]++;cnt[i + 1]++;cnt[i +2]++;                }        }        for (int i = 18 ; i < 25 ; i++)        {                if (cnt[i] && cnt[i + 1] && cnt[i + 2])                {                        cnt[i]--;cnt[i + 1]--;cnt[i + 2]--;                        dfs(cur - 3);if (found) return ;                        cnt[i]++;cnt[i + 1]++;cnt[i +2]++;                }        }}bool judge(){        for (int i = 0 ; i < 34; i++)        {                if (cnt[i] >= 2)                {                        cnt[i] -= 2;                       // printf("i = %d\n",i);                        found = false;                        dfs(12);                        if (found) return true;                        cnt[i] += 2;                }        }        return false;}int main(){        //freopen("sample.txt","r",stdin);        char res[100];        bool flag;        int kase = 1,mj[20];        while (scanf("%s",res) != EOF)        {                if (res[0] == 0) break;                printf("Case %d:",kase++);                mj[0] = id(res);                for (int i = 1; i < 13; i++)                {                        scanf("%s",res);                        mj[i]= id(res);                }                flag = false;                for (int i = 0; i < 34; i++)                {                        memset(cnt,0,sizeof(cnt));                        for (int j = 0 ; j < 13; j++)                                cnt[mj[j]]++;                        if (cnt[i] >= 4) continue;                        cnt[i]++;                        if (judge())                        {                                flag = true;                                printf(" %s",mahjong[i]);                        }                        cnt[i]--;                }                if (flag) putchar(\n);                else printf(" Not ready\n");        }        return 0;}

 

UVA 11210 Chinese Mahjong