标签存档：搜索策略

[ZOJ 3300 Mahjong]暴力DFS

【题目大意】

给出13张牌（1~9）,问摸到什么牌能赢。把所有方案在同一行输出。

【算法分析】

暴力DFS，其实有更好的复杂度为O(9*9)的方法，GDKOI上有原题。。。

但是这题规模太小了，直接暴力

【CODE】

#include #include #include #include using namespace std;

int a[20],h[20],num;
bool flag;

void dfs(int i){
    if (flag) return;
    if (num==0){
        flag=true;
        return;
    }   
    while (h[i]==0) i++;
    if (h[i]>=3){
        h[i]-=3;
        num-=3;
        dfs(i);
        h[i]+=3;
        num+=3;
    }   
    if (h[i] && h[i+1] && h[i+2]){
        h[i]–; h[i+1]–; h[i+2]–;
        num-=3;
        dfs(i);
        num+=3;
        h[i]++; h[i+1]++; h[i+2]++;
    }   
}   

bool tryit(){
    flag=false;
    num=12;
    dfs(1);
    return flag;
}   

bool solve(){
    memset(h,0,sizeof(h));
    for (int i=1;i<=14;i++){
        h[a[i]]++;
      }   
    for (int i=1;i<=9;i++)
      if (h[i]>4) return false;
    for (int i=1;i<=9;i++)
      if (h[i]>=2){
          h[i]-=2;
          if (tryit()) return true;
          h[i]+=2;
      }   
    return false;
}   

int main(){
    for (;;){
        if (scanf("%d",&a[1])==EOF) break;
        for (int i=2;i<=13;i++) scanf("%d",&a[i]);
        bool st=false;
        for (int i=1;i<=9;i++){
            a[14]=i;
            if (solve()){
                if (st) printf(" ");
                printf("%d",i);
                st=true;
            }   
        }   
        printf("n");
    }   
}