麻将的玩法规则众多,核心的玩法是一致的,本文将根据联发科2017年编程挑战赛的复赛题规则来实现。
算法实现思路
1、普通牌型为3n+2的形式,和龙7对均为14张牌,若有杠则最多有18张牌,因此第一步可以判定,如果牌数小于14或者大于18,则必定不能胡牌;
2、对牌进行从小到大排序,方便后续判断。如果手牌数是14张,可以先判定是否是龙7对(对对胡),其特点是每张奇数位的牌都和它后一位的牌相等。如果不是对对胡,则进入步骤3;
3、3n+2形式的普通牌型里面有一个对子,因此判断是不是胡牌牌型,可以先找出其中的一个对子。一张牌可能有2张也可能有4张,可以组成对子也可能组成暗杠或者杠,又或者是和后面的牌组成顺子。不管情况有多少种,对子一定是出现在重复的牌之中,只要每次遍历去除一个对子即可。接下来进入步骤4;
4、去除一个对子后,判定是否是3n牌型,即是否是全部由顺子或者暗杠组成。由于牌已经经过排序,所以只要观察第一张牌即可。
- 如果第一张牌的数量只有一张或者两张,则这张牌必须和后面的牌组成顺子,否则不能胡牌。如果存在这样的顺子,去除这个顺子
- 如果第一张牌的数量有三张或者四张,则可能组成一个暗杠,或者是和后面的牌组成顺子(先不考虑有杠的情况),去除这个暗杠(顺子)
一直循环以上的判断,满足条件则去掉这三张牌,直到牌数为0时,返回“胡牌”,否则回到步骤3中,将之前去除的对子放回,继续删除下一个对子。如果步骤3中尝试过所有的对子还没能满足胡牌条件时,则返回“不胡牌”;
5、如果牌数为15张,则至少包含一个4张牌的杠,否则不胡牌。如果包含多个杠,则依次遍历删除一个杠,再进入步骤3,判断是不是3n牌型。如果遍历完所有的杠后还不能胡牌,则返回“不胡牌”;
6、如果牌数是16张,则至少包含2个杠,依次遍历删一对杠的组合,余下同步骤5类似。同理,牌数为17张和18张时方法类似。
C++源代码
#include <iostream>
#include <vector>
#include <algorithm>
using std::vector;
using std::cout;
template <typename T>
void showVector(vector <T> & lst);
vector <int> findReptPos(vector <char> & lst);
bool isDDH(const vector <char> & lst);
bool isHU3N(vector <char> & lst);
vector <char> delDUI(const vector <char> & lst, const int x);
bool is3N(vector <char> lst);
int numOfFirst(vector <char> lst);
bool checkGroup(vector <char> lst, const int num);
void delGroup(vector <char> & lst, const int num);
vector <char> delGANG(const vector <char> & lst, const int x);
vector <int> findGangPos(const vector <char> & lst);
int main(int argc, char **argv)
{
char *mahjong = argv[1];
vector <char> lst;
for (int i = 0; mahjong[i] != '\0'; ++i)
{
lst.push_back(mahjong[i]);
}
std::sort(lst.begin(), lst.end()); // 从小到大排序
/*cout << "sort: ";
showVector(lst);*/
int num = lst.size(); // 麻将牌数量
if ((num < 14) || (num > 18))
{
cout << "BAD";
return 0;
}
if (num == 14) // 14张牌,2种胡牌法
{
if (isDDH(lst)) // 如果是对对胡
{
cout << "GOOD";
return 0;
}
if (isHU3N(lst))
{
cout << "GOOD";
}
else
{
cout << "BAD";
}
return 0;
}
if (num == 15)
{
vector <int> pos = findGangPos(lst); // 查找杠的位置
if (pos.size() < 1)
{
cout << "BAD";
}
else
{
// 依次删除一个杠,再判断是否是3N牌型
for (int i = 0; i < pos.size(); ++i)
{
vector <char> newLst = delGANG(lst, pos[i]);
/*cout << "delGANG/";
showVector(newLst);*/
if (isHU3N(newLst))
{
cout << "GOOD";
return 0;
}
}
cout << "BAD";
}
}
if (num == 16)
{
vector <int> pos = findGangPos(lst); // 查找杠的位置
if (pos.size() < 2) // 少于2个杠肯定不胡牌
{
cout << "BAD";
}
else
{
// 依次删除不同的2个杠组合,再判断是否是3N牌型
for (int i = 0; i < pos.size() - 1; ++i)
{
for (int j = i + 1; j < pos.size(); ++j)
{
// 注意先删除后一个杠,否则位置会变动
vector <char> newLst1 = delGANG(lst, pos[j]);
vector <char> newLst2 = delGANG(newLst1, pos[i]);
/*cout << "delGANG/";
showVector(newLst2);*/
if (isHU3N(newLst2))
{
cout << "GOOD";
return 0;
}
}
}
cout << "BAD";
}
}
if (num == 17)
{
vector <int> pos = findGangPos(lst); // 查找杠的位置
if (pos.size() < 3) // 少于3个杠肯定不胡牌
{
cout << "BAD";
}
else
{
// 依次删除不同的3个杠组合,再判断是否是3N牌型
for (int i = 0; i < pos.size() - 2; ++i)
{
for (int j = i + 1; j < pos.size() - 1; ++j)
{
for (int k = j + 1; k < pos.size(); ++k)
{
// 注意先删除后一个杠,否则位置会变动
vector <char> newLst1 = delGANG(lst, pos[k]);
vector <char> newLst2 = delGANG(newLst1, pos[j]);
vector <char> newLst3 = delGANG(newLst2, pos[i]);
/*cout << "delGANG/";
showVector(newLst3);*/
if (isHU3N(newLst3))
{
cout << "GOOD";
return 0;
}
}
}
}
cout << "BAD";
}
}
if (num == 18)
{
vector <int> pos = findGangPos(lst); // 查找杠的位置
if (pos.size() != 4) // 不是4个杠肯定不胡牌
{
cout << "BAD";
}
else
{
// 直接删除4个杠
vector <char> newLst1 = delGANG(lst, pos[3]);
vector <char> newLst2 = delGANG(newLst1, pos[2]);
vector <char> newLst3 = delGANG(newLst2, pos[1]);
vector <char> newLst4 = delGANG(newLst3, pos[0]);
/*cout << "delGANG/";
showVector(newLst4);*/
if (newLst4[0] == newLst4[1])
{
cout << "GOOD";
}
else
{
cout << "BAD";
}
}
}
return 0;
}
// 显示列表内容
template <typename T>
void showVector(vector <T> & lst)
{
vector <T>::iterator iter; // 迭代器
for (iter = lst.begin(); iter != lst.end(); iter++)
{
cout << *iter << " ";
}
cout << "\n";
}
// 查找重复牌的位置
vector <int> findReptPos(vector <char> & lst)
{
vector <int> pos; // 储存重复牌的位置
int temp_pos = 0;
if (lst.size() <= 1) // 牌数小于等于1,直接返回
{
return pos;
}
// lst.size() >= 2
vector <char>::iterator iter2;
iter2 = lst.begin();
++iter2; // 迭代器不支持算数运算,只能++/--/advance链式操作
if (lst.front() == *iter2)
{
pos.push_back(temp_pos);
}
vector <char>::iterator it_front;
vector <char>::iterator it_back;
for (auto iter1 = iter2; iter1 != (--lst.end()); iter1++) // 从第二位到倒数第二位
{
++temp_pos; // 位置更新
it_front = iter1; --it_front;
it_back = iter1; ++it_back;
// 不等于前面的且等于后面的
if ((*iter1 != *it_front) && (*iter1 == *it_back))
{
pos.push_back(temp_pos);
}
}
return pos;
}
// 是否是对对胡
bool isDDH(const vector <char> & lst)
{
vector <char> newLst = lst;
for (int i = 0; i <= 12; ++i)
{
if (newLst[i] != newLst[i + 1])
{
return false;
}
++i;
}
return true;
}
// 是否是普通牌型3n
bool isHU3N(vector <char> & lst)
{
vector <int> pos = findReptPos(lst); // 找重复牌的位置
for (int i = 0; i < pos.size(); ++i) // 依次去掉重复的对子
{
vector <char> newLst = delDUI(lst, pos[i]); // 删除一对牌
/*cout << "delDUI/";
showVector(newLst);*/
if (is3N(newLst))
{
return true;
}
}
return false;
}
// 是否是N个顺子或者暗杠
bool is3N(vector <char> lst)
{
if (lst.size() % 3 != 0)
{
return false;
}
while (lst.size() > 0)
{
if (lst.size() >= 3)
{
int num = numOfFirst(lst); // 计算第一张牌的重复数量
if (checkGroup(lst, num)) // 检查是否有第一个顺子或者暗杠
{
delGroup(lst, num); // 删除这组顺子或者暗杠
}
else
{
return false;
}
}
/*cout << "//";
showVector(lst);*/
}
return true;
}
// 检查是否有第一个顺子或者暗杠
bool checkGroup(vector <char> lst, const int num)
{
if ((num == 1) && (lst[1] == lst[0] + 1))
{
// 第二个数可能有重复情况
for (int i = 2; i < lst.size(); ++i)
{
if (lst[i] != lst[1])
{
if (lst[i] == lst[0] + 2)
{
return true;
}
else
{
return false;
}
}
}
}
if ((num == 2) && (lst[2] == lst[1] + 1))
{
// 第三个数可能有重复情况
for (int i = 3; i < lst.size(); ++i)
{
if (lst[i] != lst[2])
{
if (lst[i] == lst[1] + 2)
{
return true;
}
else
{
return false;
}
}
}
}
if (num >= 3)
{
return true;
}
return false;
}
// 删除这组顺子或者暗杠
void delGroup(vector <char> & lst, const int num)
{
if (num == 1)
{
vector <char>::iterator iter = ++lst.begin();
for (int i = 2; i < lst.size(); ++i)
{
++iter;
if (lst[i] == (1 + lst[1]))
{
lst.erase(iter);
lst.erase(lst.begin());
lst.erase(lst.begin());
break;
}
}
}
if (num == 2)
{
vector <char>::iterator iter = ++(++lst.begin());
for (int i = 3; i < lst.size(); ++i)
{
++iter;
if (lst[i] == (1 + lst[2]))
{
lst.erase(iter);
lst.erase(++lst.begin()); // 删除第二位的牌
lst.erase(++lst.begin());
break;
}
}
}
if (num >= 3)
{
lst.erase(lst.begin());
lst.erase(lst.begin());
lst.erase(lst.begin());
}
}
// 计算第一张牌的重复数量
int numOfFirst(vector <char> lst)
{
if (lst[0] != lst[1])
{
return 1;
}
if ((lst[0] == lst[1]) && (lst[1] != lst[2]))
{
return 2;
}
if (lst[0] == lst[2])
{
if (lst.size() == 3)
{
return 3;
}
if ((lst.size() >= 4) && (lst[2] != lst[3])) // lst[3]一定保证size>=4
{
return 3;
}
}
if ((lst[0] == lst[3]) && (lst.size() >= 4))
{
return 4;
}
return 0;
}
// 删除x和x+1位置的一对牌
vector <char> delDUI(const vector <char> & lst, const int x)
{
vector <char> newLst;
for (int i = 0; i < lst.size(); ++i)
{
if ((i != x) && (i != (x + 1)))
{
newLst.push_back(lst[i]);
}
}
return newLst;
}
// 删除起始位置为x的杠(4张牌)
vector <char> delGANG(const vector <char> & lst, const int x)
{
vector <char> newLst;
for (int i = 0; i < lst.size(); ++i)
{
if ((i < x) || (i > x + 3))
{
newLst.push_back(lst[i]);
}
}
return newLst;
}
// 查找杠的位置
vector <int> findGangPos(const vector <char> & lst)
{
vector <int> pos;
int temp_pos = 0;
if (lst.size() < 4)
{
return pos;
}
for (int i = 0; i < lst.size() - 3; ++i)
{
if (lst[i] == lst[i + 3])
{
pos.push_back(temp_pos);
}
++temp_pos; // 位置更新
}
return pos;
}
程序运行结果
程序从命令行参数取得输入数据,数据为一个字符串,代表一副牌。若这副牌达到胡牌条件,输出GOOD,否则输出BAD。