読者です 読者をやめる 読者になる 読者になる

UVa11818 Mouse and a Cheese

問題
http://uva.onlinejudge.org/external/118/11818.html

概要
3×3のグリッドが有る。各グリッドは合計12本のスティックで区切られている。鼠とチーズがこのグリッド上のいずれかのマスに存在して、鼠はスティックが外されている部分のみ通過できる。
SOHAとTARAが交互にスティックを外していくゲームをする。鼠がチーズまでたどり着けるようになったとき、その時スティックを外した人物が勝者となる。はじめに既に取られているスティックが入力されるので、両者が最善を尽くしたとき、勝利する人物を挙げよ。ただしはじめから鼠がチーズに到達できる場合は "No cheese!" と出力せよ。

解法
スティックをビットとして状態に持ったビットDPをする。到達可能かの判定でBFSをしたいのでスティックの状態をグラフに落とす必要がある。はじめに取り外されているスティックも存在するので、それが予め考慮されたグラフにエッジを一本ずつ追加している。

あと一本のスティックを取り除けば鼠がチーズに到達できる状況では、その一本を取り除くことが最善手である。つまり場面に残されたスティックのうち、勝つ事ができる取り除き方が一つでもあれば、そのターンの人間が勝者である。プレイヤーが交互に切り替わるので結果も交互に切り替わる。

反省
途中で解答方針変えたりしてたせいでコードに無駄な部分が多い気がする。ビットとエッジの変換が愚直で下手だと思う。

#include <bits/stdc++.h>
using namespace std;
  
int const dir[] = {-1,3,-3,1};
  
typedef pair<int, int> P;
#define X first
#define Y second
  
#define STICKS (12)
int mem[1<<STICKS][2];
int S, C;
  
inline int get_num(P p) {
  return p.Y*3 + p.X + 1;
}
  
inline void add_edge(vector<int> * const G, int a, int b) {
  G[a].push_back(b);
  G[b].push_back(a);
}
  
int to_bit(int a, int b) {
  if(a == 1 && b == 2) return 0;
  if(a == 2 && b == 3) return 1;
  if(a == 4 && b == 5) return 2;
  if(a == 5 && b == 6) return 3;
  if(a == 7 && b == 8) return 4;
  if(a == 8 && b == 9) return 5;
  if(a == 1 && b == 4) return 6;
  if(a == 2 && b == 5) return 7;
  if(a == 3 && b == 6) return 8;
  if(a == 4 && b == 7) return 9;
  if(a == 5 && b == 8) return 10;
  if(a == 6 && b == 9) return 11;
  return -1;
}
  
int get_stick_bit(P *line) {
  if(line[0]>line[1]) swap(line[0], line[1]);
  int pos = get_num(line[0]);
  int difx = line[1].X - line[0].X;
  int dify = line[1].Y - line[0].Y;
  if(difx == 0) { return to_bit(pos-1, pos); }
  else if(dify == 0) { return to_bit(pos-3, pos); }
  else assert(false);
}
  
void bit_to_edge(vector<int> * const G, int i) {
  switch(i) {
  case 0: add_edge(G, 1, 2); break;
  case 1: add_edge(G, 2, 3); break;
  case 2: add_edge(G, 4, 5); break;
  case 3: add_edge(G, 5, 6); break;
  case 4: add_edge(G, 7, 8); break;
  case 5: add_edge(G, 8, 9); break;
  case 6: add_edge(G, 1, 4); break;
  case 7: add_edge(G, 2, 5); break;
  case 8: add_edge(G, 3, 6); break;
  case 9: add_edge(G, 4, 7); break;
  case 10: add_edge(G, 5, 8); break;
  case 11: add_edge(G, 6, 9); break;
  }
}
  
bool bfs(const vector<int> * const G) {
    
  bool vis[10] = {}; // 1 - origin
  vis[S] = true;
  queue<int> Q;
  Q.push(S);
  while(!Q.empty()) {
    int pos = Q.front(); Q.pop();
    for(int i=0; i<G[pos].size(); i++) {
      if(vis[G[pos][i]]) continue;
      vis[G[pos][i]] = true;
      if(G[pos][i] == C) return true;
      Q.push(G[pos][i]);
    }
  }
    
  return false;
}
  
bool rec(const vector<int> * const G, int bits, int player) {
  bool ret = false;
  if(mem[bits][player] != -1) return mem[bits][player];
  if(bfs(G)) return false;
  for(int i=0; i<STICKS; i++) {
    if(!((bits >> i) & 1)) {
      vector<int> nG[10];
      for(int j=0; j<10; j++) nG[j] = G[j];
      bit_to_edge(nG, i);
      ret = ret || !rec(nG, bits|(1<<i), !player);
    }
  }
  return mem[bits][player] = ret;
}
  
int main() {
  int Tc; cin >> Tc;
    
  for(int T=1; T<=Tc; T++) {
    vector<int> G[10];
    int R; cin >> S >> C >> R;
    int bits = 0;
    for(int i=0; i<R; i++) {
      P line[2];
      cin >> line[0].X >> line[0].Y >> line[1].X >> line[1].Y;
      int get = get_stick_bit(line);
      bit_to_edge(G, get); bits |= 1<<get;
    } // for i
    cout << "Case " << T << ": ";
    if(bfs(G)) {
      cout << "No Cheese!" << endl;
    }
    else {
      memset(mem, -1, sizeof mem);
      if(rec(G, bits, false)) cout << "SOHA" << endl;
      else cout << "TARA" << endl;
    }
  } // for T
    
  return 0;
}