0043 - Puzzle
#include <iostream> #include <string> using namespace std; int Check(int number[]) { int sum=0; for (int i=1; i<10; ++i) sum+=number[i]; return sum; } void dfs(int number[], bool answer_flg[], int i) { if ( !Check(number) ) answer_flg[i]=true; else { for (int j=1; j<10; ++j) if (number[j] >= 3) { number[j]-=3; dfs(number,answer_flg,i); number[j]+=3; } for (int j=3; j<10; ++j) if (number[j-2]>=1 && number[j-1]>=1 && number[j]>=1) { --number[j-2]; --number[j-1]; --number[j]; dfs(number,answer_flg,i); ++number[j-2]; ++number[j-1]; ++number[j]; } } } void Slove(string hand) { int number[10]={0}; bool answer_flg[10]={false}, kong_flg=false, flg=false; for (int i=0; i<hand.size(); ++i) ++number[hand[i]-'0']; for (int i=1; i<10; ++i) { if (number[i] == 4) kong_flg=true; else for (int j=1; j<10; ++j) { ++number[i]; if (number[j] >= 2) { number[j]-=2; dfs(number,answer_flg,i); number[j]+=2; } --number[i]; } } for (int i=1; i<10; ++i) if ( answer_flg[i] ) { if (!flg) { cout << i; flg=true; } else cout << " " << i; } if (!flg) cout << "0"; cout << endl; } int main(void) { string hand; while (cin >> hand) Slove(hand); return 0; }
再帰で全探索。