live archive 5023 History of Dots

問題概要

異なる色の玉が出会うとどのような変換がおきるかという法則が与えられる。
玉が減ったり、増えたりしない。（色が変わるだけ）
今の玉の状態が与えらる。
そして、初期状態の候補が与えられる。
それぞれの候補に対して、今の状態になりうるか答えよ。

解法

メモ化探索。
変換を逆順に適用し、今の状態から実現可能な状態を先に列挙した。
普通にそれぞれの色の玉が何個あるかを状態にした。

ソース

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<string>
#include<sstream>
#include<set>
#include<map>

#define REP(i, b, n) for(int i = b; i <(int)n; i++)
#define rep(i, n) REP(i, 0, n)
#define FOR(it, o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end();++it)


using namespace std;

const int N = 5;

class State{
public:
  int t[N];
  State(){
    rep(i, N){
      t[i] = 0;
    }
  }
  void out(){
    rep(i, N){
      cout << t[i] << ' ';
    }
    cout << endl;
  }
  bool operator<(const State &s)const{
    rep(i, N){
      if(t[i] != s.t[i])return t[i] < s.t[i];
    }
    return false;
  }
};

State conv(string s){
  State ret;
  int now = 0;
  rep(i, s.length()){
    if(s[i] >= '0' && s[i] <= '9'){
      ret.t[now] = s[i] - '0';
      now++;
    }
  }
  return ret;
}

set<State> used;
map<pair<int, int>, pair<int, int> > M;
int n, k, end;
void solve(State &s){
  used.insert(s);
  rep(i, k){
    if(s.t[i]==0)continue;
    REP(j, i, k){
      if(s.t[j]==0)continue;
      pair<int, int> tmp = make_pair(i, j);
      if(M.find(tmp) == M.end())continue;
      
      State next = s;
      pair<int, int> t = M[tmp];
      next.t[i]--;
      next.t[j]--;
      if(next.t[j] < 0)continue;
      next.t[t.first]++;
      next.t[t.second]++;
      if(used.find(next) != used.end())continue;
      solve(next);
    }
  }
}
int main(){
  string s;
  while(getline(cin, s)){
    M.clear();
    used.clear();
    string target;
    vector<State> start;
    istringstream iss(s);
    iss >> n >> k >>end >> target;
    end--;
    string tmp;
    vector<pair<int, int> > trans;
    int a, b, c, d;
    while(iss >> a >> b >> c >> d){
      if(a > b)swap(a, b);
      if(c > d)swap(c, d);
      a--;
      b--;
      c--;
      d--;
      M[make_pair(c, d)] = make_pair(a, b);
    }
    getline(cin, s);
    rep(i, s.length()){
      if(s[i] == ')')s[i] = ' ';
    }
    istringstream iss2(s);
    while(iss2 >>tmp){
      start.push_back(conv(tmp));
    }
    State tar = conv(target);
    solve(tar);
    rep(i, start.size()){
      if(i != 0)cout << ' ';
      State tmp;
      if(used.find(start[i]) == used.end())cout << 0;
      else cout << 1;
    }
    cout <<endl;
  }
  return 0;
}