Chinese Mahjong(中国麻将)题解

Chinese Mahjong

1：每次读入13张牌，然后我们从34张牌中依次选取一张牌，看是否听这张牌，是否听这张牌，我们可以直接将这张牌直接加入到原来的13张牌中，看是否可以胡牌就行。

2：现在我们来思考一下递归的过程，首先我们选出两张牌作为对子，当这张牌的张数大于等于2的时候，将这张牌拥有的张数减去2，假如我们有多张牌可以作为将，我们一次之选其中一张，其他的牌作为刻子或者是顺子。然后选出3对刻子或者是顺子，从第0层开始递归找刻子或者是顺子，当这张牌的张数大于等于3的时候，将这张牌的张数减去3，然后递归到下一层，我们将这里做一个标记为true,当递归的层数到3的时候，我们也做一个标记为true,最后返回就行

3：关于听牌，如果是34张麻将，我们可以用一个一维数组将这些麻将存下来，这样也相当于麻将的字符串和下标的数字一一对应，当我们读入的时候，利用strcmp(a,b)==0这个函数，如果当前读入的字符串和保存的相等就返回他的下标，否则就返回-1.

int convert(const char* s){
    for(int i=0;i<34;i++)
       if(strcmp(mahjong[i],s)==0)return i;
    return -1;
}
int cnt[34];
int main(){
   char s[100];
   int a[13];
   while(scanf("%s",s)==1){
       if(s[0]=='0')break;//如果最后输入0的时候，就结束。注意是s[0]
       for(int i=1;i<13;i++){
          scanf("%s",s);
          a[i]=convert(s);
       }
   }
}

4：

(1) 本题几个需要注意的地方，就是回溯的时候，我们如果每一次再递归到下一层和最后递归到第三层的时候我们都返回的话，最后回溯的时候cnt[]是没有还原我们输入的哪个模样的，所以我们每一次的听牌的时候要将cnt[]数组重新初始化并重新读入。

(2) 如果不想每一次都初始话和读入的话，我们就读入依次cnt[],这就一定要保证我每一次做完后回溯一定要将cnt[]还原到原来的模样，所以我们再递归到下一层和递归到第三层的时候，我们用flag记录成true,表示这一层我们来过，最后回溯完全之后我们只要返回flag的值就行了。

总而言之就是每一次的cnt[]数组一定是和刚输入的是一样的，不能被改变，改变了，回溯一定要完全。

5：每一种牌只有4张，所以如果一张牌他出现了4次，这张牌是不听任何牌的。

下面附上两种不同回溯方式的代码，细品

只读入一次cnt数组

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

const char* mahjong[] = {
	"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","XI","NAN","BEI",
	"ZHONG","FA","BAI"
};

int convert(const char* s) {
	for (int i = 0; i < 34; i++) {
		if (strcmp(mahjong[i], s) == 0)return i;
	}
	return -1;
}

int cnt[40];
bool search(int dep) {
	int i;
	bool flag=false;
	for (i = 0; i < 34; i++)
		if (cnt[i] >= 3) {
			if (dep == 3) flag=true;;
			cnt[i] -= 3;
			if (search(dep + 1)) flag=true;
			cnt[i] += 3;
		}
	for (i = 0; i <= 24; i++)
		if (i % 9 <= 6 && cnt[i] >= 1 && cnt[i + 1] >= 1 && cnt[i + 2] >= 1) {
			if (dep == 3) flag=true;
			cnt[i]--; cnt[i + 1]--; cnt[i + 2]--;
			if (search(dep + 1)) flag=true;
			cnt[i]++; cnt[i + 1]++; cnt[i + 2]++;
		}
    if(flag) return true;
	return false;
}
bool check() {
	int i;
	bool flag=false;
	for (i = 0; i < 34; i++)
		if (cnt[i] >= 2) {
			cnt[i] -= 2;
			if (search(0)) flag=true;
			cnt[i] += 2;
		}
	if(flag)return true;
	return false;
}

int main() {
	char s[100];
	int mj[15];
	//bool ok;//判断是否胡牌
	int k = 0;

	while (scanf("%s", s) == 1) {
		if (s[0] == '0') break;
		mj[0] = convert(s);
		for (int i = 1; i < 13; i++) {
			scanf("%s", s);
			mj[i] = convert(s);
		}
		printf("Case %d:", ++k);
		bool ok = false;
		//只读入一次cnt数组
		memset(cnt, 0, sizeof(cnt));
		for (int j = 0; j < 13; j++)cnt[mj[j]]++;
		
		for (int i = 0; i < 34; i++) {
			if (cnt[i] >= 4)continue;
			cnt[i]++;
			if (check()) {
				ok = true;
				printf(" %s", mahjong[i]);
				/*for (int i = 0; i < 34; i++)
					cout << cnt[i] << " ";
					cout<<endl;*/
			}
			cnt[i]--;
		}
		if (!ok)printf(" Not ready");
		printf("\n");
	}
	return 0;
}

没回溯干净，每一次都要读入

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

const char* mahjong[] = {
	"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","XI","NAN","BEI",
	"ZHONG","FA","BAI"
};

int convert(char* s) {
	for (int i = 0; i < 34; i++) {
		if (strcmp(mahjong[i], s) == 0)return i;
	}
	return -1;
}

int cnt[40];
bool search(int dep) {
	int i;
	for (i = 0; i < 34; i++)  
		if (cnt[i] >= 3) {
			if (dep == 3)return true;
			cnt[i] -= 3;
			if (search(dep + 1))return true;
			cnt[i] += 3;
		} 
	for (i = 0; i <= 24; i++)  
		if (i % 9 <= 6 && cnt[i] >= 1 && cnt[i + 1] >= 1 && cnt[i + 2] >= 1) {
			if (dep == 3)return true;
			cnt[i]--; cnt[i + 1]--; cnt[i + 2]--;
			if (search(dep + 1))return true;
			cnt[i]++; cnt[i + 1]++; cnt[i + 2]++;
		}
	return false;
}
bool check() {
	int i;
	for (i = 0; i < 34; i++)  
		if (cnt[i] >= 2) {
			cnt[i] -= 2;
			if (search(0))return true;
			cnt[i] += 2;
		}
	return false;
}

int main() {
	char s[100];
	int mj[15];
	//bool ok;//判断是否胡牌
	int k = 0;
	
	while(scanf("%s",s)==1){
		if(s[0]=='0') break;
		mj[0]=convert(s);
		for(int i=1;i<13;i++){
			scanf("%s",s);
			mj[i]=convert(s);
		}
		printf("Case %d:",++k);
		bool ok=false;
		for(int i=0;i<34;i++){
			memset(cnt,0,sizeof(cnt));
			for(int j=0;j<13;j++)cnt[mj[j]]++;
			if(cnt[i]>=4)continue;//这一条语句不一样，必须加上，否测WA
			cnt[i]++;
			if(check()){
				ok=true;
				printf(" %s",mahjong[i]);
			}
			//c[i]--;这一条语句可有可无，我一开始写的时候就没有加
		}
		if(!ok)printf(" Not ready");
		printf("\n");
	}
	return 0;
}