前言
麻将，起源于中国，是一种中国古人发明的博弈游戏，流行于华人文化圈中。经过多年发展，形成多种地区特色的玩法，麻将的胡牌也有一定特定的组合。
这里就复盘一个关于四川麻将胡牌的问题，题目来源： 一人麻将。
四川麻将
题目
时间限制: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;
}
