HDU 4431 Mahjong (DFS，暴力枚举，剪枝)

题意：给定 13 张麻将牌，问你是不是“听”牌，如果是输出“听”哪张。

析：这个题，很明显的暴力，就是在原来的基础上再放上一张牌，看看是不是能胡，想法很简单，也比较好实现，结果就是TLE，一直TLE，这不科学啊。。。

好不容易写出来的，竟然TLE。。。心痛。就是先确定一个将牌，然后再对刻子和顺子进行分析，其实是要剪枝的，就是在如果有1张或者两张牌，而你又不能构成刻子的时候，就要返回false，因为这就已经没解了。

这一个剪枝，就AC了。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <stack>
using namespace std ;

typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 10 + 5;
const int mod = 1e9 + 7;
const char *mark = "+-*";
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
int n, m;
inline bool is_in(int r, int c){
    return r >= 0 && r < n && c >= 0 && c < m;
}
const char* mahjong[] = {
    "1m", "2m", "3m", "4m", "5m", "6m", "7m", "8m", "9m",
    "1s", "2s", "3s", "4s", "5s", "6s", "7s", "8s", "9s",
    "1p", "2p", "3p", "4p", "5p", "6p", "7p", "8p", "9p",
    "1c", "2c", "3c", "4c",
    "5c", "6c", "7c"
};
map<string, int> mp;
inline void init(){
    for(int i = 0; i < 34; ++i)
        mp[string(mahjong[i])] = i;
}
int c[35];

bool dfs(int d){
    for(int i = 0; i < 34; ++i){
        int cnt = 0;
        if(c[i] >= 3){
        if(d == 3) return true;
        ++cnt;
        c[i] -= 3;
        if(dfs(d+1)){ c[i] += 3;  return true; }
        c[i] += 3;
        }

        if(i <= 24 && i % 9 <= 6 && c[i] >= 1 && c[i+1] >= 1 && c[i+2] >= 1){
            ++cnt;
            if(d == 3)   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];
        }
        if(cnt == 0 && c[i])  return false; //这种牌有但是不符合顺子或者刻子结束这层搜索  
        if(c[i])  break; //这里剪枝是因为上面的搜索下次遍历的时候还会继续从他这遍历，所以就不用继续下去了
    }
    return false;
}

inline bool check(){
    for(int i = 0; i < 34; ++i){
        if(c[i] >= 2){
            c[i] -= 2;
            if(dfs(0)){ c[i] += 2;   return true; }
            c[i] += 2;
        }
    }
    return false;
}
int ans[50];

inline bool solvefood(){
    int food[35];
    memcpy(food, c, sizeof(c));
    int cnt = 0;
    for(int i = 0; i < 20; i += 9){
        --food[i], cnt += food[i];
        if(food[i] < 0) return false;
    }
    for(int i = 8; i < 30; i += 9){
        --food[i], cnt += food[i];
        if(food[i] < 0) return false;
    }
    for(int i = 27; i < 34; ++i){
        --food[i], cnt += food[i];
        if(food[i] < 0)  return false;
    }
    return cnt == 1;
}

inline bool solveseven(){
    for(int i = 0; i < 34; ++i)
        if(c[i] != 2 && c[i] != 0)  return false;
    return true;
}

int main(){
    char s[10];
    init();
    int T;  scanf("%d", &T);
    while(T--){
        memset(c, 0, sizeof(c));
        for(int i = 0; i < 13; ++i){
            scanf("%s", s);
            ++c[mp[string(s)]];
        }

        int cnt = 0;
        for(int i = 0; i < 34; ++i){
            if(c[i] >= 4)  continue;
            ++c[i];
            if(solvefood()) ans[cnt++] = i;
            else if(solveseven())  ans[cnt++] = i;
            else if(check())  ans[cnt++] = i;
            --c[i];
        }

        if(!cnt)  puts("Nooten");
        else{
            printf("%d", cnt);
            for(int i = 0; i < cnt; ++i)
                printf(" %s", mahjong[ans[i]]);
            printf("
");
        }
    }
    return 0;
}

HDU 4431 Mahjong (DFS，暴力枚举，剪枝)

相关推荐