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;

}

巴特西

UVa 11210 Chinese Mahjong （暴力，递归寻找）

最新文章

热门文章