首页 > ACM题库 > HDU-杭电 > HDU 4431-Mahjong-模拟-[解题报告]HOJ
2015
07-16

HDU 4431-Mahjong-模拟-[解题报告]HOJ

Mahjong

问题描述 :

Japanese Mahjong is a four-player game. The game needs four people to sit around a desk and play with a set of Mahjong tiles. A set of Mahjong tiles contains four copies of the tiles described next:
Yukari's Birthday

One to nine Man, which we use 1m to 9m to represent;
Yukari's Birthday

One to nine Sou, which we use 1s to 9s to represent;
Yukari's Birthday

One to nine Pin, which we use 1p to 9p to represent;
Yukari's Birthday

Character tiles, which are:Ton, Nan, Sei, Pei, Haku, Hatsu, Chun, which we use 1c to 7c to represent.

A winning state means a set of 14 tiles that normally contains a pair of same tiles (which we call "eyes") and four melds. A meld is formed by either three same tiles(1m, 1m, 1m or 2c, 2c, 2c for example) or three continuous non-character tiles(1m, 2m, 3m or 5s, 6s, 7s for example).

However, there are two special winning states that are different with the description above, which are:
"Chii Toitsu", which means 7 different pairs of tiles;
"Kokushi Muso", which means a set of tiles that contains all these tiles: 1m, 9m, 1p, 9p, 1s, 9s and all 7 character tiles. And the rest tile should also be one of the 13 tiles above.

And the game starts with four players receiving 13 tiles. In each round every player must draw one tile from the deck one by one. If he reaches a winning state with these 14 tiles, he can say "Tsu Mo" and win the game. Otherwise he should discard one of his 14 tiles. And if the tile he throws out can form a winning state with the 13 tiles of any other player, the player can say "Ron" and win the game.

Now the question is, given the 13 tiles you have, does there exist any tiles that can form a winning state with your tiles?

(Notes: Some of the pictures and descriptions above come from Wikipedia.)

输入:

The input data begins with a integer T(1≤T≤20000). Next are T cases, each of which contains 13 tiles. The description of every tile is as above.

输出:

The input data begins with a integer T(1≤T≤20000). Next are T cases, each of which contains 13 tiles. The description of every tile is as above.

样例输入:

2
1s 2s 3s 2c 2c 2c 2p 3p 5m 6m 7m 1p 1p
1p 1p 2p 3p 4s 5s 6s 7c 7c 3s 3s 2m 2m

样例输出:

2 1p 4p
Nooten

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents   
by—cxlove 

题目;给出麻将的13张牌,问再抓一张什么牌,可以胡~~~

http://acm.hdu.edu.cn/showproblem.php?pid=4431 

表示麻将一点都不会,简单看了下题,然后听victoria说了下,就开始搞了。

枚举所有的牌,然后判断14张牌有没有胡

首先是判断一下13么和7小对,这个比较好判断

其中7小对victoria的规则和题目说的有点不一样,导致WA了一次,题目要求7小对是不同的,也就是有4张牌一样不算两个对

然后是普通的胡法,感觉非常不好写,由于 可以是顺 子或者3个的,所以只能搜索了

结果还T了,自己太随意+太紧了。

整体的编码难度不大,思路也比较清晰

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
map<string,int>m;
void Init()
{
    m["1m"]=1;m["2m"]=2;m["3m"]=3;
    m["4m"]=4;m["5m"]=5;m["6m"]=6;
    m["7m"]=7;m["8m"]=8;m["9m"]=9;
    m["1s"]=10;m["2s"]=11;m["3s"]=12;
    m["4s"]=13;m["5s"]=14;m["6s"]=15;
    m["7s"]=16;m["8s"]=17;m["9s"]=18;
    m["1p"]=19;m["2p"]=20;m["3p"]=21;
    m["4p"]=22;m["5p"]=23;m["6p"]=24;
    m["7p"]=25;m["8p"]=26;m["9p"]=27;
    m["1c"]=28;m["2c"]=29;m["3c"]=30;
    m["4c"]=31;m["5c"]=32;m["6c"]=33;
    m["7c"]=34;
}
int c[35];int b[14];
int c13[13]={1,9,10,18,19,27,28,29,30,31,32,33,34};
//13幺
bool judge1()
{
    int c1=0,c2=0;
    for(int i=0;i<13;i++)
    {
        if(c[c13[i]]) c1++;
        if(c[c13[i]]>1) c2++;
    }
    if(c1==13&&c2==1) return true;
    return false;
}
//7小对
bool judge2()
{
    for(int i=0;i<14;i+=2)
    {

        if((i&&b[i]==b[i-1])||b[i]!=b[i+1]) return false;
    }
    return true;
}
bool flag;
bool check(int idx)
{
    if(idx>=1&&idx<=7) return true;
    if(idx>=10&&idx<=16) return true;
    if(idx>=19&&idx<=25) return true;
    return false;
}
void dfs(int idx,int k1,int k2)
{
    if(flag) return;
    if(k1>4||k2>1) return ;
    if(idx==14)
    {
        if(k1==4&&k2==1){flag=true;}
        return ;
    }
    for(int i=1;i<=34;i++)
    {
        int mark=0;
        if(c[i]>=3) {c[i]-=3;mark++;dfs(idx+3,k1+1,k2);c[i]+=3;}
        if(c[i]>=2) {c[i]-=2;mark++;dfs(idx+2,k1,k2+1);c[i]+=2;}
        if(check(i)&&c[i]&&c[i+1]&&c[i+2]) {c[i]--;c[i+1]--;c[i+2]--;mark++;dfs(idx+3,k1+1,k2);c[i]++;c[i+1]++;c[i+2]++;}
        if(c[i]&&mark==0) return ;
        if(c[i]) break;
    }
}
int a[14];
int slove()
{

    memcpy(b,a,sizeof(a));
    sort(b,b+14);
    mem(c,0);
    for(int i=0;i<14;i++)
    {
        c[b[i]]++;
        if(c[b[i]]>4)return false;
    }
    if(judge1()) return true;
    if(judge2()) return true;
    flag=false;
    dfs(0,0,0);
    return flag;
}

int main()
{
    m.clear();
    Init();
    int t;
    cin>>t;
    while(t--)
    {
        for(int i=0;i<13;i++)
        {
            string s;
            cin>>s;
            a[i]=m[s];
        }
        int ans[50],cnt=0;
        for(int i=1;i<=34;i++)
        {
            a[13]=i;
            if(slove()) ans[cnt++]=i;
        }
        if(cnt==0) cout<<"Nooten"<<endl;
        else
        {
            cout<<cnt;
            for(int i=0;i<cnt;i++)
            {
                for(map<string,int>::iterator it=m.begin();it!=m.end();it++)
                {
                    if(it->second==ans[i])
                    {
                        cout<<" "<<(it->first);
                        break;
                    }
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/8122258