Tamflexの貯蔵庫

やる気のない備忘録

aoj 0043

パズル | Aizu Online Judge
いわゆる麻雀.
清一色の状況下, 一向聴かどうか判定し上がり牌を出力する.
dfsで順子・暗刻を落としていき,最後に対子が残ればtrueとなるようにすればよい.
13枚しかないので1〜9について仮想的な1枚を加え,それぞれ「上がり」かどうか判定すればよい.

template<typename T> inline void priv(vector<T> a)
{
  REP(i,a.size())
    cout<<a[i]<<((i==a.size()-1)?"\n":" ");
}

bool dfs(vector<int> a)
{
  if(accumulate(a.begin(),a.end(),0) == 2)
  {
    REP(i,9) if(a[i] == 2) return true;
    return false;
  }
  REP(i,9)
  {
    if(a[i] == 0) continue;
    if(a[i] >= 3)
    {
      a[i] -= 3;
      if(dfs(a)) return true;
      a[i] += 3;
    }
  }
  REP(i,7)
  {
    if(a[i]>0 && a[i+1]>0 && a[i+2]>0)
    {
      a[i]--;a[i+1]--;a[i+2]--;
      if(dfs(a)) return true;
      a[i]++;a[i+1]++;a[i+2]++;
    }
  }
  return false;
}

void solve(string s)
{
  vector<int> a(9,0);
  vector<int> ans;
  REP(i,s.size()) a[s[i]-'1']++;
  REP(i,9)
  {
    if(a[i] == 4) continue;
    a[i]++;
    if(dfs(a)) ans.push_back(i+1);
    a[i]--;
  }
  if(ans.empty()) cout << "0" << "\n";
  else priv(ans);
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  while(cin >> s) solve(s);
  return 0