UVA 11210 Problem C Chinese Mahjong
UVA 11210 Problem C Chinese Mahjong
http://uva.onlinejudge.org/external/112/11210.html
問題概要
麻雀で次なにがくれば上がるか求めよ。
解法
全探索。
最後にくる牌を決め打ち。
練習中牌に番号を振ってやればかきやすいところをstringのまましたあげく、
探索中に必要な牌を追加していく方法でもちろん実装できなかった。
実装問題もちゃんと実装する前に、どのような実装が一番適してるかある程度考えたあと、
書くべきと思った。
焦ってもなにも得られない。
ソース
#include<iostream> #include<string> #include<cstdio> #include<sstream> #define REP(i,b,n) for(int i=b;i<(int)n;i++) #define rep(i,n) REP(i,0,n) using namespace std; inline int conv(const string &s){ if(s == "DONG")return 40; if(s == "NAN")return 50; if(s == "XI")return 60; if(s == "BEI")return 70; if(s == "ZHONG")return 80; if(s == "FA")return 90; if(s == "BAI")return 100; int base = 0; if(s[1] == 'S'){ base = 10; } if(s[1] == 'W'){ base = 20; } return (base + s[0] - '0'); } inline string conv(int &id){ string ret; ret += '0' + id%10; if(id < 10){ ret += 'T'; } else if(id < 20){ ret += 'S'; } else if(id < 30){ ret += 'W'; } else { if(id == 40)ret = "DONG"; if(id == 50)ret = "NAN"; if(id == 60)ret = "XI"; if(id == 70)ret = "BEI"; if(id == 80)ret = "ZHONG"; if(id == 90)ret = "FA"; if(id == 100)ret = "BAI"; } return ret; } const int N = 101; int t[N]; bool dfs(int pos, bool used){ if(pos == N){ if(used)return true; else return false; } if(t[pos] == 0){ if(dfs(pos+1, used))return true; return false; } if(!used && t[pos] >= 2){ t[pos]-= 2; if(dfs(pos, true))return true; t[pos]+= 2; } if(t[pos] >= 3){ t[pos] -= 3; if(dfs(pos, used))return true; t[pos] += 3; } if(pos+2 < N && t[pos] > 0 && t[pos+1] > 0 && t[pos+2] > 0){ t[pos]--; t[pos+1]--; t[pos+2]--; if(dfs(pos, used))return true; t[pos]++; t[pos+1]++; t[pos+2]++; } return false; } int main(){ string s; int tc = 0; while(getline(cin, s)){ if(s == "0")break; tc++; cout << "Case " << tc << ": "; int inp[N]; rep(i, N)inp[i] = 0; stringstream ss(s); while(ss >> s){ inp[conv(s)]++; } bool first = true; rep(i, N){ if( i < 40 && i%10 == 0){ continue; } if(i >= 40 && i%10 != 0){ continue; } rep(j, N){ t[j] = inp[j]; } t[i]++; if(t[i] <=4){ if(dfs(0, false)){ if(!first)cout << ' '; cout << conv(i); first = false; } } } if(first)cout << "Not ready"; cout << endl; } return 0; }