UVa 10111 - Find the Winning Move

Find the Winning Move
http://uva.onlinejudge.org/external/101/10111.html

問題概要

4目並べで次どのような行動すれば勝てますか？
勝てる手を左上から順番にみて、一番最初のものを出力せよ。
引き分けまたは負ける場合は#####と出力せよ。
与えられる盤面はお互い2手すすめた後のものである。

解法

ゲーム理論
メモ化
二人零和有限確定完全情報ゲーム

• 二人であり
• 両方勝ちや負けということはなく（お互いの利益の和は常に0）
• いつか終わる（盤面が埋め尽くされる）
• 自分の手を決める時、すべての情報が明かされている。

状態数は3^16だけど、
ありえない状態とか、この問題の場合、
2手進んだ状態から与えられるので正確には、
3^12くらい。

#include<iostream>
#include<algorithm>
#include<map>
#include<cassert>

#define REP(i, b, n) for(int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair

using namespace std;
const int INF = 10000;
const int n = 4;
class State{
public:
  char t[n][n];
  bool operator<(const State &s)const{
    rep(i, n){
      rep(j, n){
	if(t[i][j] != s.t[i][j])return t[i][j] > s.t[i][j];
      }
    }
    return false;
  }
  int whoWin(){
    rep(i, n){
      bool winR = true, winC = true;
      char cR = t[i][0], cC = t[0][i];
      rep(j, n){
	if(cR != t[i][j]){
	  winR = false;
	}
	if(cC != t[j][i])winC = false;
      }
      if(winR && cR == 'o')return 1;
      if(winR && cR == 'x')return 0;
      if(winC && cC == 'o')return 1;
      if(winC && cC == 'x')return 0;
    }
    bool winT = true, winB = true;
    char cT = t[0][0], cB = t[n-1][0];
    rep(i, n){
      if(cT != t[i][i])winT = false;
      if(cB != t[n-1-i][i])winB = false;
    }
    if(winT && cT == 'o')return 1;
    if(winT && cT == 'x')return 0;
    if(winB && cB == 'o')return 1;
    if(winB && cB == 'x')return 0;
    return -1;
  }
};  

map<State, int > M[2];
int solve(State &s, int turn, bool first){
  if(!first && M[turn].find(s) != M[turn].end())return M[turn][s];
  int who = s.whoWin();
  if(who != -1){
    assert(!first);
    int ret = 0;
    if(who == turn)ret = 2;
    M[turn][s] = ret;
    return ret;
  }
  char c;
  if(turn == 0)c = 'x';
  else c = 'o';
  int ret = -1, nextTurn = (turn+1)%2;
  int maxi = 0;
  rep(i, 4){
    rep(j, 4){
      if(s.t[i][j] != '.')continue;
      s.t[i][j] = c;
      int tmp = solve(s, nextTurn, false);
      s.t[i][j] = '.';
      if(tmp == 2){
	tmp = 0;
      }
      else if(tmp == 0)tmp = 2;
      else if(tmp == 1)tmp = 1;
      ret = max(tmp, ret);
      if(ret == 2){
	if(first)cout << '(' << i << ',' << j << ')' << endl;
	break;
      }
      if(ret == 2)break;
    }
    if(ret == 2)break;
  }
  if(ret == -1)ret = 1;
  M[turn][s] = ret;
  return ret;
}

int main(){
  char c;
  while(cin >> c){
    if(c == '$')break;
    State s;
    rep(i, n){
      rep(j, n){
	cin >> s.t[i][j];
      }
    }
    if(solve(s, 0, true) != 2){
      cout << "#####" << endl;
    }
  }
}