AOJ2102 Rummy

問題

9枚のカードがある。そのうち3枚が、同じ色で、かつ同じ数字または連番のとき、3枚を1セットとみなす。3セット揃っているかどうか調べよ。数字は1〜9までの値で、連番とは3,4,5のようなものを指す。9,1,2は連番ではないことに注意せよ。

• 

解答

9個あるカードを3分割する全探索をする。3^9で解が求まる。

解法選びが問題の肝。

bool check(vector<deque<pair<int, char>>> const& cards) {
  rep(i, 3) {
    assert(cards[i].size() == 3);
    char col = cards[i][0].second;
    vector<int> is;
    for(auto p: cards[i]) {
      if(col != p.second) return false;
      is.push_back(p.first);
    }
    sort(is.begin(), is.end());
    if(!((is[0] + 1 == is[1] && is[1] + 1 == is[2])
      || (is[0] == is[2]))) return false;
  }
  return true;
}

bool dfs(vector<pair<int, char>> const& vs, vector<deque<pair<int, char>>>& cards, int idx) {
  if(idx == vs.size()) {
    if(check(cards)) return true;
    return false;
  }
  rep(i, 3) {
    if(cards[i].size() < 3) {
      cards[i].push_back(vs[idx]);
      if(dfs(vs, cards, idx + 1)) return true;
      cards[i].pop_back();
    }
  }
  return false;
}

int main() {

  int Tc; cin >> Tc;
  while(Tc--) {
    vector<pair<int, char>> vs;
    vector<int> a(9); vector<char> b(9);
    rep(i, 9) cin >> a[i];
    rep(i, 9) cin >> b[i];
    rep(i, 9) vs.emplace_back(a[i], b[i]);
    vector<deque<pair<int, char>>> cards(3);
    cout << dfs(vs, cards, 0) << endl;
  }
  
  return 0;
}