UVa10111

問題文イミフ。英語力の不足を実感。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 4;

class State{
public:
  char g[N][N];
  int hash(void){
    int h = 0;
    int w = 1;
    for(int i=0; i<N; ++i){
      for(int j=0; j<N; ++j){
        if( g[i][j] == '.' ) h += 0 * w;
        if( g[i][j] == 'o' ) h += 1 * w;
        if( g[i][j] == 'x' ) h += 2 * w;
        w *= 3;
      }
    }
    return h;
  }
  bool fin(char c){
    for(int i=0; i<N; ++i){
      bool a, b;
      a = b = true;    
      for(int j=0; j<N; ++j){
        a = a && g[i][j] == c;
        b = b && g[j][i] == c;
      }
      if( a || b )return true;
    }
    
    bool a, b;
    a = b = true;    
    for(int i=0; i<N; ++i){
      a = a && g[i][i] == c;
      b = b && g[i][N-1-i] == c;
    }
    if( a || b )return true;
    
    return false;
  }
};

const int T = 43046721+1;
int t[T];
char color[] = {'x', 'o'};

const int W = 0, L = 1;

int rec(State s, int c)
{
  if( s.fin( color[ c ^ 1 ] ) ) return L;
  int h = s.hash();
  if( t[h] != -1 ) return t[h];

  int mn = L;
  for(int i=0; i<N; ++i){
    for(int j=0; j<N; ++j){
      if( s.g[i][j] != '.' ) continue;
      s.g[i][j] = color[ c ];
      mn = min( mn, rec(s, c^1)^1 );
      s.g[i][j] = '.';
    }
  }

  return t[h] = mn;
}

int main(void)
{
  char c;
  while( cin >> c && c == '?' ){
    
    fill( t, t + T, -1 );

    State s;
    for(int i=0; i<N; ++i){
      for(int j=0; j<N; ++j){
        cin >> s.g[i][j];
      }
    }

    pair<int, int> p = make_pair(-1, -1);
    for(int i=0; i<N; ++i){
      for(int j=0; j<N; ++j){
        if( s.g[i][j] == '.' ){
          s.g[i][j] = 'x';
          if( rec(s, 1) == L ){
            p = make_pair(i, j);
            i = j = N; break;
          }
          s.g[i][j] = '.';
        }
      }
    }
    if( p.first < 0 || p.second < 0 )cout << "#####" << endl;
    else cout << "(" << p.first << "," << p.second << ")" << endl;
  }
  return 0;
}