PKU 2361 Tic Tac Toe

http://poj.org/problem?id=2361
tic tac toeというゲームの盤面が与えられる。
この盤面が、ゲームの終了状態または、途中の状態としてありうるかを判定するという問題。

似たような問題がありましたよね。
PKU3075でした。

set<string> app;

bool ok(const string&in){
  bool ret=false;
  rep(i,3){
    ret|=in[i*3]!='.'&&in[i*3]==in[i*3+1]&&in[i*3+1]==in[i*3+2];
    ret|=in[i]!='.'&&in[i]==in[i+3]&&in[i+3]==in[i+6];
  }
  ret|=in[0]!='.'&&in[0]==in[4]&&in[0]==in[8];
  ret|=in[2]!='.'&&in[2]==in[4]&&in[4]==in[6];
  return ret;
}

main(){
  queue<pair<int,string> >q;
  q.push(mp(0,"........."));
  while(!q.empty()){
    int c=q.front().F;
    string st=q.front().S;
    q.pop();
    if(app.count(st))continue;
    app.insert(st);
    if(ok(st))continue;
    rep(i,9){
      if(st[i]!='.')continue;
      if(c&1)st[i]='O';
      else st[i]='X';
      if(!app.count(st))q.push(mp(c+1,st));
      st[i]='.';
    }
  }
  int n;
  cin>>n;
  while(n--){
    string temp,in;
    rep(i,3){
      cin>>temp;
      in+=temp;
    }
    cout<<(app.count(in)?"yes":"no")<<endl;
  }
}