美文网首页大前端开发数据结构和算法分析程序猿阵线联盟-汇总各类技术干货
麻将胡牌问题

麻将胡牌问题

作者: Jiao123 | 来源:发表于2019-07-04 14:34 被阅读0次

    前言

    麻将，起源于中国，是一种中国古人发明的博弈游戏，流行于华人文化圈中。经过多年发展，形成多种地区特色的玩法，麻将的胡牌也有一定特定的组合。

    这里就复盘一个关于四川麻将胡牌的问题，题目来源： 一人麻将。

    四川麻将

    题目

    时间限制:10000ms
    单点时限:1000ms
    内存限制:256MB
    描述
    小Hi在北方的暖气里温暖如春，小Ho却在南方的艳阳里感受大雪纷飞。距离使得他们连一起打麻将的机会都没有，失落的小Hi一个人玩起了麻将。

    小Hi玩的是四川麻将，因此只有3种序数牌万、筒、条，每种花色一到九各4张。

    小Hi起手拥有14张牌，之后小Hi每摸一张牌后，如果没有胡牌，就出一张牌，直至胡牌或牌被摸光。反正一个人玩又赢不到小Ho的钱，因此小Hi永远也不会选择暗杠。

    胡牌的规则如下：

    手中14张牌最多只能属于两个花色。

    手中14张牌的牌型须满足下列两个条件之一：

    1）3 + 3 + 3 + 3 + 2，其中的3代表一坎（指同花色且同数字、或同花色且数字相连的三张牌），其中的2代表一个对子（指两张同花色且同数字的牌）。

    2）2 × 7，即14张牌构成7个对子，特别的，四张花色数字全相同的牌可以看作两个对子。
    万、筒、条分别记为a, b, c，以下对能胡牌的牌型举出一些例子：

    a1 a2 a3 a5 a5 a5 c3 c4 c5 c5 c6 c7 c7 c7

    b2 b2 b5 b5 b7 b7 b8 b8 c1 c1 c2 c2 c3 c3

    现给出小Hi的起手牌，并按顺序给出场上其余小Hi将要摸的牌。（小Hi只拿出了一副麻将的一部分牌玩，因此并不是每张牌都会被摸到。）

    请计算小Hi最早在摸第几张牌之后就可能胡牌，天胡（起手牌构成胡牌牌型）记为第0张。无法胡牌输出-1。

    输入
    每张牌用a, b或c其后紧接一个数字1-9表示。

    第一行是一个正整数n (n <= 94)，代表将要摸的牌。

    第二行是14张手牌。

    第三行是n张底牌，按摸牌顺序给出。

    输出
    输出一个整数，代表最早在摸第几张牌之后可能胡牌，无法胡牌输出-1。

    样例输入

    12
    a1 a1 a1 a2 a3 a4 a5 a6 a7 a8 a9 a9 a9 c1
    c2 b1 b2 b4 b5 c1 b7 b8 a1 a2 a3 a4

    样例输出

    6

    分析

    首先，这道题的数据量很小，牌数一共只有96张，每钟花色也只有36张，所以不用过多考虑算法可能超时的问题，只需要把逻辑理清楚即可。

    然后不要被打牌的流程所禁锢，就是摸一张必须打一张出去，这样每次的最佳打法很难确定。其实对于我们来说是拥有上帝视角的，知道后面所有牌的顺序，所以不用每摸一张牌就考虑最佳14张牌的排布。

    那么，我们只需要摸一张就往数据集里添加一张牌，然后看是否能找出14张牌来胡牌就行了。

    int main(int argc, const char * argv[]) {
    cin>>n;
    for (int i = 0; i < 14; i++) {
        string m;
        cin>>m;
        input(m);
    }
    vector<string> tm;
    for (int i = 0; i < n; i++) {
        string m;
        cin>>m;
        tm.push_back(m);
    }
    int res = 0;
    bool flag = check();
    while (!flag && res < n) {
        input(tm[res]);
        res++;
        flag = check();
    }
    if (flag) {
        cout<<res<<endl;
    }
    else {
        cout<<-1<<endl;
    }
    return 0;
}

    接下来确定胡牌的组合，一种是7对，另一种就是常规的1个对子，4砍。没有对子，那么铁定就胡不了，还有四川麻将最对只留两个花色，check函数就主要处理7对和胡不了的情况。

    bool check()
{
    int da = 0;
    int db = 0;
    int dc = 0;
    for (int i = 1; i < 10; i++) {
        da += a[i] / 2;
        db += b[i] / 2;
        dc += c[i] / 2;
    }
    // a+b;
    if (da + db >= 7) {
        return true;
    }
    if (da + db > 0 && subCheck(a, b)) {
        return true;
    }
    
    // a+c;
    if (da + dc >= 7) {
        return true;
    }
    if (da + dc > 0 && subCheck(a, c)) {
        return true;
    }
    // b+c;
    if (db + dc >= 7) {
        return true;
    }
    if (db + dc > 0 && subCheck(b, c)) {
        return true;
    }
    
    return false;
}

    最后需要判断常规的1+4的胡牌情况，首先把对子确定了，然后去查砍牌，查到4组就可以确定胡牌了。在不考虑3张一样牌成砍的情况下，查砍牌直接暴力从1开始就行了。

                for (int j = 1; j <= 7; j++) {
                int minX = min(min(tx[j], tx[j+1]), tx[j+2]);
                count += minX;
                tx[j] -= minX;
                tx[j+1] -= minX;
                tx[j+2] -= minX;
                
                int minY = min(min(ty[j], ty[j+1]), ty[j+2]);
                count += minY;
                ty[j] -= minY;
                ty[j+1] -= minY;
                ty[j+2] -= minY;
                
                if (count >= 4) {
                    return true;
                }
            }

    对于3张一样牌成砍的情况，需要确定是把他们合起来做砍好，还是拆开和其他牌组合好。这个就需要判断拆开后是否能多砍牌组合。比如3个三万，我需要看一万、二万、四万、五万的个数情况，确定是否拿3个三万作为一砍。

                for (int j = 1; j < 10; j++) {
                if (tx[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(tx[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        tx[j] -= 3;
                        count++;
                    }
                }
                
                if (ty[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(ty[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        ty[j] -= 3;
                        count++;
                    }
                }
            }

    整个subcheck，1+4情况：

    bool subCheck(int *x, int *y)
{
    for (int i = 1; i < 10; i++) {
        if (x[i] >= 2) {
            int tx[10], ty[10];
            for (int j = 1; j < 10; j++) {
                tx[j] = x[j];
                ty[j] = y[j];
            }
            tx[i] -= 2;
            int count = 0;
            for (int j = 1; j < 10; j++) {
                if (tx[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(tx[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        tx[j] -= 3;
                        count++;
                    }
                }
                
                if (ty[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(ty[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        ty[j] -= 3;
                        count++;
                    }
                }
            }
            
            
            for (int j = 1; j <= 7; j++) {
                int minX = min(min(tx[j], tx[j+1]), tx[j+2]);
                count += minX;
                tx[j] -= minX;
                tx[j+1] -= minX;
                tx[j+2] -= minX;
                
                int minY = min(min(ty[j], ty[j+1]), ty[j+2]);
                count += minY;
                ty[j] -= minY;
                ty[j+1] -= minY;
                ty[j+2] -= minY;
                
                if (count >= 4) {
                    return true;
                }
            }
            
        }
        if (y[i] >= 2) {
            int tx[10], ty[10];
            for (int j = 1; j < 10; j++) {
                tx[j] = x[j];
                ty[j] = y[j];
            }
            ty[i] -= 2;
            int count = 0;
            
            for (int j = 1; j < 10; j++) {
                if (tx[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(tx[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        tx[j] -= 3;
                        count++;
                    }
                }
                
                if (ty[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(ty[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        ty[j] -= 3;
                        count++;
                    }
                }
            }
            
            
            for (int j = 1; j <= 7; j++) {
                int minX = min(min(tx[j], tx[j+1]), tx[j+2]);
                count += minX;
                tx[j] -= minX;
                tx[j+1] -= minX;
                tx[j+2] -= minX;
                
                int minY = min(min(ty[j], ty[j+1]), ty[j+2]);
                count += minY;
                ty[j] -= minY;
                ty[j+1] -= minY;
                ty[j+2] -= minY;
                
                if (count >= 4) {
                    return true;
                }
            }
        }
    }
    return false;
}

    结果

    整个算法的时间复杂度为n×10×10×5，可以看到运行几乎没有耗费时间。

    完整代码：

    //
//  main.cpp
//  一人麻将
//
//  Created by Jiao Liu on 7/2/19.
//  Copyright © 2019 ChangHong. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;
int n,a[10],b[10],c[10];

bool subCheck(int *x, int *y)
{
    for (int i = 1; i < 10; i++) {
        if (x[i] >= 2) {
            int tx[10], ty[10];
            for (int j = 1; j < 10; j++) {
                tx[j] = x[j];
                ty[j] = y[j];
            }
            tx[i] -= 2;
            int count = 0;
            for (int j = 1; j < 10; j++) {
                if (tx[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(tx[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        tx[j] -= 3;
                        count++;
                    }
                }
                
                if (ty[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(ty[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        ty[j] -= 3;
                        count++;
                    }
                }
            }
            
            
            for (int j = 1; j <= 7; j++) {
                int minX = min(min(tx[j], tx[j+1]), tx[j+2]);
                count += minX;
                tx[j] -= minX;
                tx[j+1] -= minX;
                tx[j+2] -= minX;
                
                int minY = min(min(ty[j], ty[j+1]), ty[j+2]);
                count += minY;
                ty[j] -= minY;
                ty[j+1] -= minY;
                ty[j+2] -= minY;
                
                if (count >= 4) {
                    return true;
                }
            }
            
        }
        if (y[i] >= 2) {
            int tx[10], ty[10];
            for (int j = 1; j < 10; j++) {
                tx[j] = x[j];
                ty[j] = y[j];
            }
            ty[i] -= 2;
            int count = 0;
            
            for (int j = 1; j < 10; j++) {
                if (tx[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(tx[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        tx[j] -= 3;
                        count++;
                    }
                }
                
                if (ty[j] >= 3) {
                    int l = max(1, j-2);
                    int r = min(9, j+2);
                    vector<int> tmp;
                    for (int k = l; k <= r; k++) {
                        tmp.push_back(ty[k]);
                    }
                    int tCount = 0;
                    for (int k = 0; k < tmp.size()-2; k++) {
                        int minX = min(min(tmp[k], tmp[k+1]), tmp[k+2]);
                        tCount += minX;
                        tmp[k] -= minX;
                        tmp[k+1] -= minX;
                        tmp[k+2] -= minX;
                    }
                    if (tCount <= 1) {
                        ty[j] -= 3;
                        count++;
                    }
                }
            }
            
            
            for (int j = 1; j <= 7; j++) {
                int minX = min(min(tx[j], tx[j+1]), tx[j+2]);
                count += minX;
                tx[j] -= minX;
                tx[j+1] -= minX;
                tx[j+2] -= minX;
                
                int minY = min(min(ty[j], ty[j+1]), ty[j+2]);
                count += minY;
                ty[j] -= minY;
                ty[j+1] -= minY;
                ty[j+2] -= minY;
                
                if (count >= 4) {
                    return true;
                }
            }
        }
    }
    return false;
}

bool check()
{
    int da = 0;
    int db = 0;
    int dc = 0;
    for (int i = 1; i < 10; i++) {
        da += a[i] / 2;
        db += b[i] / 2;
        dc += c[i] / 2;
    }
    // a+b;
    if (da + db >= 7) {
        return true;
    }
    if (da + db > 0 && subCheck(a, b)) {
        return true;
    }
    
    // a+c;
    if (da + dc >= 7) {
        return true;
    }
    if (da + dc > 0 && subCheck(a, c)) {
        return true;
    }
    // b+c;
    if (db + dc >= 7) {
        return true;
    }
    if (db + dc > 0 && subCheck(b, c)) {
        return true;
    }
    
    return false;
}

void input(string m)
{
    if (m[0] == 'a') {
        a[m[1]-'0']++;
    }
    if (m[0] == 'b') {
        b[m[1]-'0']++;
    }
    if (m[0] == 'c') {
        c[m[1]-'0']++;
    }
}

int main(int argc, const char * argv[]) {
    cin>>n;
    for (int i = 0; i < 14; i++) {
        string m;
        cin>>m;
        input(m);
    }
    vector<string> tm;
    for (int i = 0; i < n; i++) {
        string m;
        cin>>m;
        tm.push_back(m);
    }
    int res = 0;
    bool flag = check();
    while (!flag && res < n) {
        input(tm[res]);
        res++;
        flag = check();
    }
    if (flag) {
        cout<<res<<endl;
    }
    else {
        cout<<-1<<endl;
    }
    return 0;
}

    相关文章

      网友评论

        本文标题：麻将胡牌问题

        本文链接：https://www.haomeiwen.com/subject/gfilhctx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        大前端开发

        数据结构和算法分析

        程序猿阵线联盟-汇总各类技术干货

        关于我们|服务条款|联系我们|麻将胡牌问题|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！