UVA11210 题解

思路分析

一道大模拟。

一共只有 \(34\) 种牌，因此可以一次判断是否“听”这些牌。比如，为了判断是否“听”一万，只需要判断自己拿到这张一万后能否可以继续和牌。这样，问题就转化成了给定 \(14\) 张牌，判断是否可以和牌。为此，我们可以递归求解：首先将两张牌作为“将”，然后每次选 \(3\) 张作为刻子或者顺子。

选将有 \(5\) 种方法（一万、二万、三万、四万、五万都可以做将）。如果选五万做将，一万要么属于一个刻子，要么属于一个顺子。注意，这是不必考虑其他拍是如何形成刻子或者顺子的，否则会出现重复枚举。

为了快速选出将、刻子和顺子，我们用一个 \(34\) 维向量来表示状态，即每种牌所剩余的张数。除了第一次直接枚举将牌之外，每次只需要就考虑编号最小的牌，看它是否形成刻子或者顺子，并且递归判断。但是本题有个陷阱，每一种牌只有 \(4\) 张，所以 1S1S1S1S 是不“听”任何牌的。

程序实现

#include <bits/stdc++.h>
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", "NAN", "XI", "BEI",
	"ZHONG", "FA", "BAI"
};
int kase, c[34], mj[15];
bool ok;
char s[100];
int convert(char *s) { // 预处理
	for (int i = 0; i < 34; i++)
		if (!strcmp(mahjong[i], s))
			return i;
	return -1;
}
bool search(int dep) { // 回溯法递归
	for (int i = 0; i < 34; i++)
		if (c[i] >= 3) { // 刻子
			if (dep == 3) return true;
			c[i] -= 3;
			if (search(dep + 1)) return true;
			c[i] += 3;
		}
	for (int i = 0; i <= 24; i++)
		if (i % 9 <= 6 && c[i] >= 1 && c[i + 1] >= 1 && c[i + 2] >= 1) { // 顺子
			if (dep == 3) return true;
			c[i]--, c[i + 1]--, c[i + 2]--;
			if (search(dep + 1)) return true;
			c[i]++, c[i + 1]++, c[i + 2]++;
		}
	return false;
}
bool check() {
	for (int i = 0; i < 34; i++)
		if (c[i] >= 2) { // 将牌
			c[i] -= 2;
			if (search(0)) return true;
			c[i] += 2;
		}
	return false;
}
int main() {
	while (scanf("%s", s) == 1) {
		if (s[0] == '0') break;
		printf("Case %d:", ++kase);
		mj[0] = convert(s);
		for (int i = 1; i < 13; i++) {
			scanf("%s", s);
			mj[i] = convert(s);
		}
		ok = false;
		for (int i = 0; i < 34; i++) {
			memset(c, 0, sizeof(c));
			for (int j = 0; j < 13; j++) c[mj[j]]++;
			if (c[i] >= 4) continue; // 每张牌最多只有4张
			c[i]++; // 假设拥有这张牌
			if (check()) { // 如果“和”了
				ok = true; // 那么听这张牌
				printf(" %s", mahjong[i]);
			}
			c[i]--;
		}
		if (!ok) printf(" Not ready");
		puts("");
	}
	return 0;
}