POJ 4049 Chess 极大极小搜索 -

题目地址：http://poj.org/problem?id=4049

男孩走最好的棋，只要有一步能赢就能赢

女孩是随意走，只有当所有局面都是男孩赢才能返回赢

一直卡在判断该局面是否赢的函数上，不能根据放置的棋子(x,y)的行列还有对角线判断是否赢

要判断所有的行列对角线才对

#include<cstdio>
#include<cstring>
#include<queue> 
#include<set> 
#include<string> 
#include<algorithm>
#include<iostream>
using namespace std;
char str[5][5];
int chess;
char boy,girl;
char will[5];
bool MinSearch(int x,int y);  //boy走最好的棋，girl不管走什么都能赢就是必 
bool MaxSearch(int x,int y);
bool check(char who)
{int tot;for(int i=1;i<=4;i++){tot=0;for(int j=1;j<=4;j++)if(str[i][j]==who) tot++;if(tot==4) return true;}for(int i=1;i<=4;i++){tot=0;for(int j=1;j<=4;j++)if(str[j][i]==who) tot++;if(tot==4) return true;}tot=0;for(int i=1;i<=4;i++)if(str[i][i]==who) tot++;if(tot==4) return true;tot=0;for(int i=1;i<=4;i++)if(str[i][5-i]==who) tot++;if(tot==4) return true;return false;
}
bool MaxSearch(int x,int y)
{if(check(girl)) { //girl win!if(will[0]=='L') return true;else             return false;}if(chess==16){if(will[0]=='T') return true;else             return false;}for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)if(str[i][j]=='.'){str[i][j]=boy; chess++;bool tmp=MinSearch(x,y);str[i][j]='.'; chess--;if(tmp==true) return true;           }return false;
} 
bool MinSearch(int x,int y)
{if(check(boy)) { //boy win！ if(will[0]=='W') return true;else             return false;}if(chess==16){if(will[0]=='T') return true;else             return false;}for(int i=1;i<=4;i++)  //girl不管怎么下男孩都能赢也就是所有下的都要INF for(int j=1;j<=4;j++)if(str[i][j]=='.'){str[i][j]=girl; chess++;bool tmp=MaxSearch(x,y);str[i][j]='.';  chess--;if(tmp==false) return false;}return true;
}
bool solve()
{for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)if(str[i][j]=='.'){str[i][j]=boy;  chess++;bool tmp=MinSearch(i,j);str[i][j]='.';  chess--;if(tmp==true) return true;  //下的第一颗棋子INF，表明必胜 }return false;
}
int main()
{int T,X,O; cin>>T;while(T--){scanf("%s",will);O=X=0;for(int i=1;i<=4;i++){scanf("%s",str[i]+1); for(int j=1;j<=4;j++)if(str[i][j]=='o') O++;else if(str[i][j]=='x') X++;}chess=X+O;if(O==X) boy='x',girl='o';else     boy='o',girl='x';if(solve()) cout<<"YES"<<endl;else        cout<<"NO"<<endl;}return 0;
}