AOJ0043

学校来たけど用事ある人全員来てなかったので図書館のPCでコーディング．

問題:Puzzle
パズルという名の麻雀,の待ち判定．
再帰のほうが無駄なくかける気がするけど，特に工夫しなくても間に合いそうなのでただの幅優先．
再帰書くの苦手なので今度再帰でも書いてみよう．
map便利ィ!!

#include <iostream>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef map<int,int> mii;

struct Node{
	mii used;
	mii leave;
};

int main(){
	string s;
	while( getline(cin,s) ){
		set<int> kai;
		mii in;
		for(int i=0; i<s.size(); ++i){
			in[s[i]-'0']++;
		}
		Node n,m;
		for(int k=0;k<=9;++k){
			n.leave = in;
			if((++n.leave[k])==5)continue;
			queue<Node> q;
			q.push(n);
			while(!q.empty()){
				n = q.front();q.pop();
				mii cnt;
				for(mii::iterator it =  n.leave.begin(); it!= n.leave.end(); ++it){
					if(it->second != 0){
						cnt[it->first]=it->second;
					}
				}
				if( cnt.size() == 1 && cnt.begin()->second == 2){
					kai.insert( k );
				}
				else{
					vector<int> ex3;
					vector<int> ren3;
					for(mii::iterator it =  n.leave.begin(); it!= n.leave.end(); ++it){
						if( it->second == 3){
							ex3.push_back(it->first);
						}
					}
					for(int i=1; i<=7; ++i){
						if( n.leave[i] &&  n.leave[i+1] &&  n.leave[i+2] ){
							ren3.push_back(i);
						}
					}
					for(int i=0;i<ex3.size();++i){
						m = n;
						m.leave[ex3[i]]-=3;
						m.used [ex3[i]]+=3;
						q.push( m );
					}
					for(int i=0;i<ren3.size();++i){
						m = n;
						m.leave[ren3[i]  ]--;
						m.leave[ren3[i]+1]--;
						m.leave[ren3[i]+2]--;
						m.used [ren3[i]  ]++;
						m.used [ren3[i]+1]++;
						m.used [ren3[i]+2]++;
						q.push( m );
					}
				}
			}
		}
		if(kai.empty()){
			cout << 0 << endl;
		}
		else{
			set<int>::iterator it=kai.begin();
			while(1){
				cout << *it;
				++it;
				if(it==kai.end())break;
				cout << " ";
			}cout << endl;
		}
	}
	return 0;
}