Uva 11210.Chinese Mahjong

632

题目


Mahjong ( ) is a game of Chinese origin usually played by four persons with tiles resembling dominoes
and bearing various designs, which are drawn and discarded until one player wins with a hand of four
combinations of three tiles each and a pair of matching tiles.
A set of Mahjong tiles will usually differ from place to place. It usually has at least 136 tiles, most
commonly 144, although sets originating from America or Japan will have more. The 136-tile Mahjong
includes:
Dots: named as each tile consists of a number of circles. Each circle is said to represent copper
(tong) coins with a square hole in the middle. In this problem, they’re represented by 1T, 2T, 3T, 4T,
5T, 6T, 7T, 8T and 9T.
Bams: named as each tile (except the 1 Bamboo) consists of a number of bamboo sticks. Each
stick is said to represent a string (suo) that holds a hundred coins. In this problem, they’re represented
by 1S, 2S, 3S, 4S, 5S, 6S, 7S, 8S and 9S.
Craks: named as each tile represents ten thousand (wan) coins, or one hundred strings of one
hundred coins. In this problem, they’re represented by 1W, 2W, 3W, 4W, 5W, 6W, 7W, 8W and 9W.
Wind tiles: East, South, West, and North. In this problem, they’re represented by DONG, NAN,
XI, BEI.
Dragon tiles: red, green, and white. The term dragon tile is a western convention introduced by
Joseph Park Babcock in his 1920 book introducing Mahjong to America. Originally, these tiles are
said to have something to do with the Chinese Imperial Examination. The red tile means you pass the
examination and thus will be appointed a government official. The green tile means, consequently you
will become financially well off. The white tile (a clean board) means since you are now doing well you
should act like a good, incorrupt official. In this problem, they’re represented by ZHONG, FA, BAI.
There are 9 3 + 4 + 3 = 34 kinds, with exactly 4 tiles of each kind, so there are 136 tiles in total.
To who may be interested, the 144-tile Mahjong also includes:
Flower tiles: typically optional components to a set of mahjong tiles, often contain artwork on
their tiles. There are exactly one tile of each kind, so 136+8=144 tiles in total. In this problem, we
don t consider these tiles.
Chinese Mahjong is very complicated. However, we only need to know very few of the rules in order
to solve this problem. A meld is a certain set of tiles in one’s hand. There are three kinds of melds
you need to know (to who knows Mahjong already, kong is not considered):
Pong: A set of three identical titles. Example: , .
Chow: A set of three suited tiles in sequence. All three tiles must be of the same suites. Sequences
of higher length are not permissible (unless it forms more than one meld). Obviously, wind tiles and
dragon tiles can never be involved in chows. Example: , .
Eye: The pair, while not a meld, is the final component to the standard hand. It consists of any
two identical tiles.
A player wins the round by creating a standard mahjong hand. That means, the hand consists of
an eye and several (possible zero) pongs and chows. Note that each title can be involved in exactly one
eye/pong/chow.
When a hand is one tile short of wining, the hand is said to be a ready hand, or more figuratively,
’on the pot’. The player holding a ready hand is said to be waiting for certain tiles. For example
is waiting for , and .
To who knows more about Mahjong: don’t consider special winning hands such as ‘ ’.


Input  


The input consists of at most 50 test cases. Each case consists of 13 tiles in a single line. The hand is
legal (e.g. no invalid tiles, exactly 13 tiles). The last case is followed by a single zero, which should not
be processed.


Output  


For each test case, print the case number and a list of waiting tiles sorted in the order appeared in
the problem

Description (1T 9T, 1S 9S, 1W 9W, DONG, NAN, XI, BEI, ZHONG, FA, BAI). Each waiting tile  


should be appeared exactly once. If the hand is not ready, print a message ‘Not ready’ without quotes.


Sample Input  


1S 1S 2S 2S 2S 3S 3S 3S 7S 8S 9S FA FA
1S 2S 3S 4S 5S 6S 7S 8S 9S 1T 3T 5T 7T
0


Sample Output  


Case 1: 1S 4S FA
Case 2: Not ready



题解


给出手中已有的牌,求再加哪些牌能 “和”

总共只有 23 张排,枚举即可
先枚举所有的可能
再枚举所有的 “将”(两张一样的)
再对剩下的牌分别用不同的方式凑成 “顺”“刻”

暴力模拟
时刻明确自己在干什么,函数分清楚就行

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 32;

const string mj[34] = {
    "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"
};
map<string,int> mjmap;

int mjlist[34];
int ans[34];
int kase = 1;

void init() {
    mjmap.clear();
    for(int i = 0;i < 34;i++)
        mjmap.insert(pair<string,int>(mj[i],i));
}

bool xp(int a = -1,int b = -1,int c = -1) {
    //删除3张可以顺或者刻牌
    if(a != -1) {
        mjlist[a]--;
        mjlist[b]--;
        mjlist[c]--;
    }

    bool empty = true;
    bool win = false;
    for(int i = 0;i < 34;i++) {
        if(mjlist[i] != 0) {
            empty = false;
            bool can = false;

            if(mjlist[i] >= 3) {
                can = true;
                if(xp(i,i,i)) {
                    win = true;
                    break;
                }
            }

            if(mjlist[i] >= 1 && (
                (i >= 0 && i <= 6) ||
                (i >= 9 && i <= 15) ||
                (i >= 18 && i <= 24)) &&
                mjlist[i + 1] >= 1 &&
                mjlist[i + 2] >= 1) {
                can = true;
                if(xp(i,i + 1,i + 2)) {
                    win = true;
                    break;
                }
            }

            if(!can)
                break;
        }
    }

    if(a != -1) {
        mjlist[a]++;
        mjlist[b]++;
        mjlist[c]++;
    }

    return empty || win;
}

bool shun(int j) {
    //用 j 做将时,是否能赢
    mjlist[j] -= 2;

    bool win = false;
    for(int i = 0;i < 34;i++)
        if(xp()) {
            win = true;
            break;
        }

    mjlist[j] += 2;
    return win;
}

bool ting(int p) {
    //判断加上编号为 p 的牌是否能赢  
    if(mjlist[p] == 4)
        return false;

    bool win = false;
    mjlist[p]++;

    for(int i = 0;i < 34;i++)
        if(mjlist[i] >= 2)
            if(shun(i)) {
                win = true;
                break;
            }

    mjlist[p]--;
    return win;

}


bool Do() {
    memset(mjlist,0,sizeof(mjlist));
    int pos = 0;

    for(int i = 0;i < 13;i++) {
        string t;
        cin >> t;
        if(t == "0")
            return false;
        mjlist[mjmap[t]]++;
    }

    for(int i = 0;i < 34;i++) {
        if(ting(i))
            ans[pos++] = i;
    }

    cout << "Case " << kase++ << ":";
    if(pos) {
        for(int i = 0;i < pos;i++)
            cout << " " << mj[ans[i]];
        cout << endl;
    } else {
        cout << " Not ready" << endl;
    }
    return true;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    init();
    while(Do());

    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论