[POJ1568]Find the Winning Move（极大极小搜索，alpha-beta剪枝，特判）

题目链接：http://poj.org/problem?id=1568

四子连珠的游戏，给一个局面，下一步是x走，问有没有必胜，如果有必胜走哪里可以必胜。

easy的模拟，需要加上alpha-beta剪枝，以及一个很神的剪枝。那就是初始局面小于等于4个棋子的时候，一定没有必胜手，这个很容易想到。

注意Min Max里ok判断的是上一步，所以inf和-inf要区分开。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <cassert>
  8 #include <cstdio>
  9 #include <bitset>
 10 #include <vector>
 11 #include <deque>
 12 #include <queue>
 13 #include <stack>
 14 #include <ctime>
 15 #include <set>
 16 #include <map>
 17 #include <cmath>
 18 using namespace std;
 19 
 20 const int maxn = 5;
 21 const int inf = (1 << 30);
 22 char G[maxn][maxn];
 23 char cmd[2];
 24 int tot, rx, ry;
 25 
 26 bool ok(int x, int y) {
 27     int flag = 1;
 28     for(int i = 0; i < 4; i++) {
 29         if(G[x][y] != G[x][i]) {
 30             flag = 0;
 31             break;
 32         }
 33     }
 34     if(flag) return 1;
 35     flag = 1;
 36     for(int i = 0; i < 4; i++) {
 37         if(G[x][y] != G[i][y]) {
 38             flag = 0;
 39             break;
 40         }
 41     }
 42     if(flag) return 1;
 43     flag = 1;
 44     for(int i = 0; i < 4; i++) {
 45         if(G[x][y] != G[i][3-i]) {
 46             flag = 0;
 47             break;
 48         }
 49     }
 50     if(flag) return 1;
 51     flag = 1;
 52     for(int i = 0; i < 4; i++) {
 53         if(G[x][y] != G[i][i]) {
 54             flag = 0;
 55             break;
 56         }
 57     }
 58     if(flag) return 1;
 59     return 0;
 60 }
 61 
 62 int Max(int x, int y, int alpha);
 63 int Min(int x, int y, int beta);
 64 
 65 int Max(int x, int y, int alpha) {
 66     if(ok(x, y)) return -inf;
 67     if(tot == 16) return 0;
 68     int ret = -inf;
 69     for(int i = 0; i < 4; i++) {
 70         for(int j = 0; j < 4; j++) {
 71             if(G[i][j] != '.') continue;
 72             G[i][j] = 'x'; tot++;
 73             int tmp = Min(i, j, ret);
 74             G[i][j] = '.'; tot--;
 75             ret = max(ret, tmp);
 76             if(ret >= alpha) return ret;
 77         }
 78     }
 79     return ret;
 80 }
 81 
 82 int Min(int x, int y, int beta) {
 83     if(ok(x, y)) return inf;
 84     if(tot == 16) return 0;
 85     int ret = inf;
 86     for(int i = 0; i < 4; i++) {
 87         for(int j = 0; j < 4; j++) {
 88             if(G[i][j] != '.') continue;
 89             G[i][j] = 'o'; tot++;
 90             int tmp = Max(i, j, ret);
 91             G[i][j] = '.'; tot--;
 92             ret = min(ret, tmp);
 93             if(ret <= beta) return ret;
 94         }
 95     }
 96     return ret;
 97 }
 98 
 99 int gao() {
100     int beta = -inf;
101     for(int i = 0; i < 4; i++) {
102         for(int j = 0; j < 4; j++) {
103             if(G[i][j] != '.') continue;
104             G[i][j] = 'x'; tot++;
105             int tmp = Min(i, j, beta);
106             G[i][j] = '.'; tot--;
107             if(tmp == inf) {
108                 rx = i; ry = j;
109                 return 1;
110             }
111         }
112     }
113     return 0;
114 }
115 
116 int main() {
117     // freopen("in", "r", stdin);
118     while(~scanf("%s", cmd) && cmd[0] != '$') {
119         tot = 16;
120         for(int i = 0; i < 4; i++) {
121             scanf("%s", G[i]);
122             for(int j = 0; j < 4; j++) {
123                 if(G[i][j] == '.') tot--;
124             }
125         }
126         if(tot <= 4) {
127             puts("#####");
128             continue;
129         }
130         if(gao()) printf("(%d,%d)
", rx, ry);
131         else puts("#####");
132     }    
133     return 0;
134 }