Poj 1568(极大极小搜索

题目：４＊４的４子棋，给出一个局面判断是否是必胜的．

思路：裸的ｍｉｎｍａｘ搜索，不过这题有个很重要的剪枝，当已经下了的子小于等于４时，是不可能必胜的（具体证明没有深究．．这种剪枝在赛场上可以二分把．．．）．我的写法没有这个剪枝直接就ｔ了．．．(估计ｈａｓｈ一下也能过，不想试了．．．）

/*
* @author:  Cwind
*/
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <set>
#include <cmath>
using namespace std;
#define IOS std::ios::sync_with_stdio (false);std::cin.tie(0)
#define pb push_back
#define PB pop_back
#define bk back()
#define fs first
#define se second
#define sq(x) (x)*(x)
#define eps (1e-6)
#define IINF (1<<29)
#define LINF (1ll<<59)
#define INF (1000000000)
#define FINF (1e3)
#define clr(x) memset((x),0,sizeof (x));
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> P;

const int maxn=6;
char B[maxn][maxn];
char r[maxn];
int searchMin();
int check(){
    bool f;
    for(int i=0;i<4;i++){
        f=1;
        for(int j=0;j<4;j++){
            if(B[i][j]!='x'){
                f=0;
                break;
            }
        }
        if(f) return 1;
        f=1;
        for(int j=0;j<4;j++){
            if(B[j][i]!='x'){
                f=0;
                break;
            }
        }
        if(f) return 1;
    }
    f=1;
    for(int j=0;j<4;j++){
        if(B[j][j]!='x'){
            f=0;
            break;
        }
    }
    if(f) return 1;
    f=1;
    for(int j=0;j<4;j++){
        if(B[j][4-j-1]!='x'){
            f=0;
            break;
        }
    }
    if(f) return 1;
    for(int i=0;i<4;i++){
        f=1;
        for(int j=0;j<4;j++){
            if(B[i][j]!='o'){
                f=0;
                break;
            }
        }
        if(f) return -1;
        f=1;
        for(int j=0;j<4;j++){
            if(B[j][i]!='o'){
                f=0;
                break;
            }
        }
        if(f) return -1;
    }
    f=1;
    for(int j=0;j<4;j++){
        if(B[j][j]!='o'){
            f=0;
            break;
        }
    }
    if(f) return -1;
    f=1;
    for(int j=0;j<4;j++){
        if(B[j][4-j-1]!='o'){
            f=0;
            break;
        }
    }
    if(f) return -1;
    return 0;
}
int count(){
    int ans=0;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            ans+=(B[i][j]=='.');
        }
    }
    return ans;
}
int searchMax(){
    int res=check();
    if(res!=0) return res;
    if(count()==0) return 0;
    int Max=-1;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(B[i][j]=='.'){
                B[i][j]='x';
                Max=max(Max,searchMin());
                B[i][j]='.';
                if(Max==1) return 1;
            }
        }
    }
    return Max;
}
int searchMin(){
    int res=check();
    if(res!=0) return res;
    if(count()==0) return 0;
    int Min=1;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(B[i][j]=='.'){
                B[i][j]='o';
                Min=min(Min,searchMax());
                B[i][j]='.';
                if(Min==-1) return -1;
            }
        }
    }
    return Min;
}
void solve(){
    if(count()>=12){
        puts("#####");
        return;
    }
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(B[i][j]=='.'){
                B[i][j]='x';
                if(searchMin()==1){
                    printf("(%d,%d)
",i,j);
                    return;
                }
                B[i][j]='.';
            }
        }
    }
    puts("#####");
}
int main(){
    freopen("/home/files/CppFiles/in","r",stdin);
    while(scanf("%s",r),r[0]=='?'){
        for(int i=0;i<4;i++){
            scanf("%s",B[i]);
        }
        solve();
    }
    return 0;
}