POJ 3317 - Stake Your Claim

http://poj.org/problem?id=3317

概要

n * n のボード上にプレイヤー0, 1 がプレイヤー0から順に交互に自分の番号を置いていく． ボードが埋まったらゲーム終了で，それぞれ連続したマスの数の最大値がそのプレイヤーの得点となる．

まだ k 個置けるようなボードの状態が与えられる． それぞれのプレイヤーが最良の手を選んでゲームを続けたとき，最初の一手とそのときに最終的に何点差で勝つ(負ける場合は負になる)かを答える．

制約

解法

ゲーム木探索．

アルファ・ベータ法 - Wikipedia を実装した．

  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 using namespace std;
  5 
  6 struct board
  7 {
  8   vector<pair<int,int> > holes;
  9   vector<int> cache;
 10   board(vector<string>& g, const vector<pair<int,int> >& h)
 11     : holes(h), cache(1<<h.size())
 12   {
 13     build_cache(g);
 14   }
 15 
 16   void build_cache(vector<string>& grid)
 17   {
 18     const int N = holes.size();
 19     for (int s = 0; s < (1<<N); s++) {
 20       const int x = __builtin_popcount(s);
 21       if (N/2 != x && (N+1)/2 != x) {
 22         continue;
 23       }
 24       for (int i = 0; i < N; i++) {
 25         grid[holes[i].first][holes[i].second] = s & (1<<i) ? '1' : '0';
 26       }
 27       cache[s] = evaluate(grid);
 28     }
 29   }
 30 
 31   static int evaluate(const vector<string>& grid)
 32   {
 33     const int H = grid.size();
 34     const int W = grid[0].size();
 35     vector<vector<int> > visited(H, vector<int>(W, false));
 36     int ans[2] = {0, 0};
 37     for (int i = 0; i < H; i++) {
 38       for (int j = 0; j < W; j++) {
 39         if (visited[i][j]) {
 40           continue;
 41         }
 42 
 43         const char c = grid[i][j];
 44         visited[i][j] = true;
 45         queue<pair<int,int> > q;
 46         q.push(make_pair(i, j));
 47         int d = 0;
 48         while (!q.empty()) {
 49           const int k = q.front().first;
 50           const int l = q.front().second;
 51           q.pop();
 52           ++d;
 53           for (int t = 0; t < 4; t++) {
 54             static const int di[] = {-1, 1, 0, 0};
 55             static const int dj[] = {0, 0, -1, 1};
 56             const int x = k + di[t];
 57             const int y = l + dj[t];
 58             if (0 <= x && x < H && 0 <= y && y < W && !visited[x][y] && grid[x][y] == c) {
 59               visited[x][y] = true;
 60               q.push(make_pair(x, y));
 61             }
 62           }
 63         }
 64         ans[c-'0'] = max(ans[c-'0'], d);
 65       }
 66     }
 67     return ans[0] - ans[1];
 68   }
 69 
 70   pair<int, pair<int,int> > alphabeta(int turn, int alpha = -1000000, int beta = 1000000, int s = 0, int t = 0) const
 71   {
 72     const int N = holes.size();
 73     if (s == (1<<N)-1) {
 74       return make_pair(turn * cache[t], make_pair(-1, -1));
 75     }
 76 
 77     pair<int,int> move(-1, -1);
 78     for (int i = 0; i < N; i++) {
 79       if (!(s & (1<<i))) {
 80         const int x = -alphabeta(-turn, -beta, -alpha, s | (1<<i), t | (turn == 1 ? 0 : (1<<i))).first;
 81         if (x > alpha) {
 82           alpha = x;
 83           move = holes[i];
 84         }
 85         if (alpha >= beta) {
 86           return make_pair(alpha, move);
 87         }
 88       }
 89     }
 90     return make_pair(alpha, move);
 91   }
 92 };
 93 
 94 int main()
 95 {
 96   int N;
 97   while (cin >> N && N != 0) {
 98     vector<string> grid(N);
 99     vector<pair<int,int> > holes;
100     int zero = 0, one = 0;
101     for (int i = 0; i < N; i++) {
102       cin >> grid[i];
103       for (int j = 0; j < N; j++) {
104         if (grid[i][j] == '.') {
105           holes.push_back(make_pair(i, j));
106         } else if (grid[i][j] == '0') {
107           ++zero;
108         } else {
109           ++one;
110         }
111       }
112     }
113 
114     const board b(grid, holes);
115     const int turn = (N*N - holes.size()) % 2 == 0 ? 1 : -1;
116     const pair<int, pair<int,int> > r = b.alphabeta(turn);
117     cout << "(" << r.second.first << "," << r.second.second << ") " << r.first << endl;
118   }
119   return 0;
120 }
poj/3317.cc