UVa11229

UVa11229

盤面の状態は 3^9 = 19683 程度。メモ化する。
引き分けの場合は後手番の勝利に含めてしまっていい。

memo[ 盤面の状態 ] = 先手の勝率
先手は勝率を最大化し、後手は勝率を最小化する。

#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <vector>

#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#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()
#define each(i, c) FOR(i, c)

typedef long long int lli;

using namespace std;

const int BIT = 19683;

double P[2][3][3];
double memo[BIT];
int g[3][3];

bool win(int p)
{
  if (g[0][0] == p && g[0][1] == p && g[0][2] == p) return true;
  if (g[1][0] == p && g[1][1] == p && g[1][2] == p) return true;
  if (g[2][0] == p && g[2][1] == p && g[2][2] == p) return true;

  if (g[0][0] == p && g[1][0] == p && g[2][0] == p) return true;
  if (g[0][1] == p && g[1][1] == p && g[2][1] == p) return true;
  if (g[0][2] == p && g[1][2] == p && g[2][2] == p) return true;

  if (g[0][0] == p && g[1][1] == p && g[2][2] == p) return true;
  if (g[0][2] == p && g[1][1] == p && g[2][0] == p) return true;

  return false;
}

bool lose(int p)
{
  return win(p ^ 1);
}

int make_bit(void)
{
  int bit = 0;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      bit = bit * 3 + g[i][j];
    }
  }
  return bit;
}

const int FIRST = 0, SECOND = 1, EMPTY = 2;

double rec(int p)
{
  const int bit = make_bit();
  double &ret = memo[bit];

  if (ret != -1) return ret;

  if (win(FIRST)) return ret = 100.0;
  if (lose(FIRST)) return ret = 0.0;
  if (count(&g[0][0], &g[3 - 1][3], EMPTY) == 0) return ret = 0.0;

  double best = (p == FIRST) ? 0 : 100.0;

  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      if (g[i][j] != EMPTY) continue;

      g[i][j] = p;
      double a = rec(p ^ 1) * P[p][i][j];

      g[i][j] = p ^ 1;
      double b = rec(p ^ 1) * (1.0 - P[p][i][j]);

      best = (p == FIRST) ? max(best, a + b) : min(best, a + b);

      g[i][j] = EMPTY;
    }
  }

  return ret = best;
}

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {
    for (int k = 0; k < 2; ++k) {
      for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
          cin >> P[k][i][j];
          P[k][i][j] /= 100.0;
        }
      }
    }

    fill(&g[0][0], &g[3 - 1][3], EMPTY);
    fill(memo, memo + BIT, -1);

    static int tc = 0;
    printf("Case #%d: %.2lf\n", ++tc, rec(0));
  }
  return 0;
}