本文主要是介绍hdu4431 Mahjong 枚举搜索。。,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
japanese麻将什么玩意。。都没有豪华七对。。。
没什么难的 就是枚举搜索了
分三种类型的胡牌
f1是七对 f2是十三幺 f3是普通的胡牌 就先找一对 再找三个三个的
就是一直超时。。在峰峰的指导下加了好多剪枝 注释都标出来了。。这样才过 而且好慢。。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;int cnt[40],res,ans[40];
map<string,int>mp;
void init()
{mp["1m"]=1; mp["1s"]=11; mp["1p"]=21;mp["2m"]=2; mp["2s"]=12; mp["2p"]=22;mp["3m"]=3; mp["3s"]=13; mp["3p"]=23;mp["4m"]=4; mp["4s"]=14; mp["4p"]=24;mp["5m"]=5; mp["5s"]=15; mp["5p"]=25;mp["6m"]=6; mp["6s"]=16; mp["6p"]=26;mp["7m"]=7; mp["7s"]=17; mp["7p"]=27;mp["8m"]=8; mp["8s"]=18; mp["8p"]=28;mp["9m"]=9; mp["9s"]=19; mp["9p"]=29;mp["1c"]=31;mp["2c"]=32; mp["3c"]=33;mp["4c"]=34;mp["5c"]=35; mp["6c"]=36;mp["7c"]=37;
}int f1()//7dui
{int a=0;for(int i=1;i<=38;i++){if(cnt[i]==2) a++;}return a==7;
}int f2()//13yao
{int i,j;for(i=0;i<30;i+=10){if(!cnt[i+1]||!cnt[i+9]) return 0;for(j=2;j<9;j++)if(cnt[i+j]) return 0;}for(i=31;i<=37;i++)if(!cnt[i]) return 0;return 1;
}int dfs()
{int i;if(res==0) return 1;for(i=1;i<30;i++){if(cnt[i]>=3){cnt[i]-=3;res-=3;if(dfs()){cnt[i]+=3;res+=3;return 1;}cnt[i]+=3;res+=3;}}for(i=1;i<30;i++){if(cnt[i]&&cnt[i+1]&&cnt[i+2]){cnt[i]--;cnt[i+1]--;cnt[i+2]--;res-=3;if(dfs()){cnt[i]++;cnt[i+1]++;cnt[i+2]++;res+=3;return 1;}cnt[i]++;cnt[i+1]++;cnt[i+2]++;res+=3;}}return 0;
}int f3()
{int i;for(i=1;i<38;i++)if(cnt[i]>=2){cnt[i]-=2;res=12;int ok=1;//这里再加一个剪枝 先找出连不成一句话的三个一样的for(int j=31;j<=37;j++){if(cnt[j]==3) res-=3;//减小dfselse if(cnt[j]) {ok=0;break;}}if(!ok) {cnt[i]+=2;continue;}if(dfs()){cnt[i]+=2;return 1;}cnt[i]+=2;}return 0;
}int main()
{int t,i,k;char s[5];init();scanf("%d",&t);while(t--){memset(cnt,0,sizeof cnt);for(i=0;i<13;i++){scanf("%s",s);cnt[mp[s]]++;}for(i=1,k=0;i<=37;i++){if(i%10==0||cnt[i]==4) continue;//如果这张牌已经有四个就不用加啦cnt[i]++;if(cnt[i]==4&&!cnt[i-1]&&!cnt[i+1]){cnt[i]--;//如果这张牌有四个 且相邻两个都没有 那一定不能胡continue;}if(f2()){ans[k++]=i;cnt[i]--;continue;}else if(cnt[i]==1&&!cnt[i-1]&&!cnt[i+1]){cnt[i]--;//判断为不是十三幺后continue;//如果这张牌只有一个 而且前后都没有 那一定不能胡}if(f1()||f3())ans[k++]=i;cnt[i]--;}if(k){// sort(ans.begin(),ans.end());//markprintf("%d",k);for(i=0;i<k;i++){if(ans[i]<10)printf(" %dm",ans[i]%10);else if(ans[i]<20)printf(" %ds",ans[i]%10);else if(ans[i]<30)printf(" %dp",ans[i]%10);else printf(" %dc",ans[i]%10);}putchar('\n');}else printf("Nooten\n");}return 0;
}
这篇关于hdu4431 Mahjong 枚举搜索。。的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!