訓練指南24頁的題 真是醉了 以為死循環了 原來是循環套的太多了 出一組樣例 500S+ 遞歸盡量減少嵌套循環 會死 我的復雜度34*14*13*12*11*10*9*8*7*6*5*4*3*2*1 提前腦子不好用啊！！！
特別注意以後回溯千萬別忘記調用函數後還要把變量改回來
#include
#include
#include
#include
#include
using namespace std;
vector have;
set ans;
int ji = 0,kase = 0;
bool zuhe(vector now)
{
int flagzong = 0;
for(int i = 0; i < now.size(); i++)
if(now[i] != 99)
{
flagzong = 1;
break;
}
if(!flagzong) return true; //終於完事了
for(int i = 0; i < now.size(); i++)
for(int j = 0; j < now.size(); j++)
for(int k = 0; k < now.size(); k++)
{
if(i == j || i == k || j == k || now[i] == 99 || now[j] == 99 || now[k] == 99) continue;
int a = now[i],b = now[j],c = now[k];
int flag = 0;
if(a == b && a == c) //刻子
{
vector now1(now);
now1[i] =99;
now1[j] =99;
now1[k] =99;
if(zuhe(now1)) return true;
}
else
if((a >= 0 && a <= 8 && b >= 0 && b <= 8 && c >= 0 && c <= 8)||(a >= 9 && a <= 17 && b >= 9 && b <= 17 && c >= 9 && c <= 17)||(a >= 18 && a <= 26 && b >= 18 && b <= 26 && c >= 18 && c <= 26)) //順子
{
if(a + 1 == b && b + 1 == c) flag = 1;
if(a + 1 == c && c + 1 == b) flag = 1;
if(b + 1 == a && a + 1 == c) flag = 1;
if(b + 1 == c && c + 1 == a) flag = 1;
if(c + 1 == a && a + 1 == b) flag = 1;
if(c + 1 == b && b + 1 == a) flag = 1;
if(flag)
{
vector now1(now);
now1[i] =99;
now1[j] =99;
now1[k] =99;
if(zuhe(now1)) return true;
}
}
}
return false;
}
bool ting(vector now) //選擇兩個牌做將
{
for(int i = 0; i < now.size(); i++)
for(int j = 0; j < now.size(); j++)
{
if(i == j || now[i] != now[j]) continue;
vector temp(now);
temp[i] = 99;
temp[j] = 99;
if(zuhe(temp)) return true;
}
return false;
}
void solve()
{
for(int i = 0; i < 34; i++)
{
int countt = 0;
for(int j = 0; j < have.size(); j++)
if(have[j] == i) countt++;
if(countt < 4)
{
vector temp(have);
temp.push_back(i);
if(ting(temp)) ans.insert(i);
}
}
}
void build(string str)
{
if(str == "DONG") have.push_back(27);
if(str == "NAN") have.push_back(28);
if(str == "XI") have.push_back(29);
if(str == "BEI") have.push_back(30);
if(str == "ZHONG") have.push_back(31);
if(str == "FA") have.push_back(32);
if(str == "BAI") have.push_back(33);
if(str[1] == 'T') have.push_back(str[0] - '0' - 1);
if(str[1] == 'S') have.push_back(str[0] - '0' + 8);
if(str[1] == 'W') have.push_back(str[0] - '0' + 17);
}
void print()
{
set::iterator it;
if(ans.empty())
{
printf(" Not ready\n");
return;
}
for(it = ans.begin(); it != ans.end(); it++)
{
printf(" ");
if((*it) >= 0 && *it <= 8) printf("%dT",(*it) + 1);
if((*it) >= 9 && *it <= 17) printf("%dS",(*it) - 8);
if((*it) >= 18 && *it <=26) printf("%dW",(*it) - 17);
if((*it) == 27) printf("DONG");
if((*it) == 28) printf("NAN");
if((*it) == 29) printf("XI");
if((*it) == 30) printf("BEI");
if((*it) == 31) printf("ZHONG");
if((*it) == 32) printf("FA");
if((*it) == 33) printf("BAI");
}
printf("\n");
return;
}
int main()
{
string str;
while(cin>>str && str != "0")
{
build(str);
ji++;
if(ji % 13 == 0)
{
solve();
printf("Case %d:",++kase);
print();
ji = 0;
have.clear();
ans.clear();
}
}
return 0;
}
以下是佳神的代碼：
#include
#include
int mj[20], cnt[35];
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 getNum(char *str) { //將牌面轉換為編號
for (int i = 0; i < 34; i++) {
if (!strcmp(mahjong[i], str)) return i;
}
}
int check2(int n) {
for (int i = 0; i < 34; i++) { //刻子
if (cnt[i] >= 3) {
if (n == 3) return 1;
cnt[i] -= 3;
if (check2(n + 1)) return 1;
cnt[i] += 3;
}
}
for (int i = 0; i <= 24; i++) { //順子
if (i % 9 <= 6 && cnt[i] && cnt[i + 1] && cnt[i + 2]) {
if (n == 3) return 1;
cnt[i]--;
cnt[i + 1]--;
cnt[i + 2]--;
if (check2(n + 1)) return 1;
cnt[i]++;
cnt[i + 1]++;
cnt[i + 2]++;
}
}
return 0;
}
int check() {
for (int i = 0; i < 34; i++) {
if (cnt[i] >= 2) {//將
cnt[i] -= 2;
if (check2(0)) return 1;
cnt[i] += 2;
}
}
return 0;
}
int main() {
char str[3];
int Case = 1;
while (scanf("%s", str) == 1) {
if (strcmp(str, "0") == 0) break;
printf("Case %d:", Case++);
mj[0] = getNum(str);
for (int i = 1; i < 13; i++) {
scanf("%s", str);
mj[i] = getNum(str);//將牌面轉化為編號
}
int flag = 0;
for (int i = 0; i < 34; i++) {//枚舉34種可能和的情況
memset(cnt, 0, sizeof(cnt));
for (int j = 0; j < 13; j++) {
cnt[mj[j]]++;//統計每張牌出現次數
}
if (cnt[i] >= 4) continue;//已出現四次則不再考慮這張牌
cnt[i]++;
if (check()) {
flag = 1;
printf(" %s", mahjong[i]);
}
}
if (!flag) printf(" Not ready/n");
else printf("/n");
}
return 0;
}
