解いた問題

5/24/2011

UVa11818


#include <iostream>
#include <vector>
#include <map>
#include <stack>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(),(c).end()

using namespace std;

class DisjointSet{
public: 
  vector<int> rank, p;
  DisjointSet(){}
  DisjointSet(int size){
    rank.resize(size, 0);
    p.resize(size, 0);
  }
  void make(int a){
    rank[a] = 0;
    p[a] = a;
  }
  void join(int a, int b){
    link(find(a), find(b));
  }
  int find(int a){
    return (a == p[a])? a : p[a] = find(p[a]);
  }
  bool isSameSet(int a, int b){
    return find(a) == find(b);
  }
  void link (int a, int b){
    if(rank[a] > rank[b]) p[b] = a;
    else{
      p[a] = b;
      if(rank[a] == rank[b]) rank[b]++;
    }
  }
};

pair<int, int> sep[12];
int no[4][4][4][4];

class State{
public:
  DisjointSet ds;
  int bit;
  State(){
    bit = (1 << 12) - 1;
    ds = DisjointSet(9);
    for(int i=0; i<9; ++i) ds.make(i);
    return ;
  }
  bool is_connected(int a, int b){
    return ds.isSameSet(a, b);
  }
  void remove_bar(int n){
    bit ^= (1 << n);
    ds.join( sep[n].first, sep[n].second );
    return ;
  }
  bool is_remained(int n){
    return bit & (1 << n);
  }
};

void init(void)
{
  sep[0]  = make_pair(0, 1);
  sep[1]  = make_pair(1, 2);
  sep[2]  = make_pair(0, 3);
  sep[3]  = make_pair(1, 4);
  sep[4]  = make_pair(2, 5);
  sep[5]  = make_pair(3, 4);
  sep[6]  = make_pair(4, 5);
  sep[7]  = make_pair(3, 6);
  sep[8]  = make_pair(4, 7);
  sep[9]  = make_pair(5, 8);
  sep[10] = make_pair(6, 7);
  sep[11] = make_pair(7, 8);

#define ref_no(a, b, c, d) no[a][b][c][d] = no[c][d][a][b]
  ref_no(1, 0, 1, 1) = 0;
  ref_no(2, 0, 2, 1) = 1;
  ref_no(0, 1, 1, 1) = 2;
  ref_no(1, 1, 2, 1) = 3;
  ref_no(2, 1, 3, 1) = 4;
  ref_no(1, 1, 1, 2) = 5;
  ref_no(2, 1, 2, 2) = 6;
  ref_no(0, 2, 1, 2) = 7;
  ref_no(1, 2, 2, 2) = 8;
  ref_no(2, 2, 3, 2) = 9;
  ref_no(1, 2, 1, 3) = 10;
  ref_no(2, 2, 2, 3) = 11;

  return ;
}

const int W = 0, L = 1;
const int T = 1 << 12;
int t[T];

int rec(State s, const int M, const int C)
{
  if( s.is_connected(M, C) )return L;
  if( t[ s.bit ] != -1 )return t[ s.bit ];
  State tmp = s;
  int r = L;
  for(int i=0; i<12; ++i){
    if( !s.is_remained(i) )continue;
    s.remove_bar(i);
    r = min( r, rec(s, M, C)^1 );
    s = tmp;
  }
  return t[ s.bit ] = r;
}

int main(void)
{
  init();

  int tc, cnt = 0;
  cin >> tc;
  while( tc-- ){
    fill( t, t + T, -1 );
    int m, c, b;
    State s;
    cin >> m >> c >> b;
    --m; --c;
    while( b-- ){
      int i, j, k, l;
      cin >> i >> j >> k >> l;
      s.remove_bar( no[i][j][k][l] );
    }

    cout << "Case " << ++cnt << ": " << flush;
    if( s.is_connected(m, c) ) cout << "No Cheese!" << endl;
    else cout << ( rec(s, m, c) == W ? "SOHA" : "TARA" ) << endl;
  }
  return 0;
}

0 件のコメント :

コメントを投稿