POJ 1085 Triangle War 极大极小+剪枝 -

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

极大极小排序，就是注意当一方有个三角形后可以再走一次

有个小小小的问题结果卡一天了......

代码如下：

#include<cstdio>
#include<cstring>
#include<queue> 
#include<set> 
#include<string> 
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=20+5;
const int Triangle[9][3]={ {1,2,3},{4,5,8},{3,5,6},{6,7,9},{10,11,16},{8,11,12},{12,13,17},{9,13,14},{14,15,18}
};
const int Edge[19][2]={ //每条边连接的顶点 {0,0},{1,2},{1,3},{2,3},{2,4},{2,5},{3,5},{3,6},{4,5},{5,6},{4,7},{4,8},{5,8},{5,9},{6,9},{6,10},{7,8},{8,9},{9,10}
};
int edge;
bool edges[20];  //18个边 
int Num(){       //三角形总数 int cnt=0;for(int i=0;i<9;i++){bool ok=true;for(int j=0;j<3&&ok;j++)if(edges[Triangle[i][j]]==false) ok=false;if(ok) cnt++;}return cnt;	
}
bool MinSearch(int A,int B);
bool MaxSearch(int A,int B);
bool MaxSearch(int A,int B)
{if(A>=5) return true;if(B>=5) return false;if(edge==18) return A>B;for(int i=1;i<=18;i++)if(!edges[i]){edges[i]=true; edge++;int nt=Num(); bool tmp;if(nt>A+B) tmp=MaxSearch(nt-B,B);   //三角形变多了 else       tmp=MinSearch(A,B);edges[i]=false; edge--;if(tmp==true) return true;}return false;
}
bool MinSearch(int A,int B)
{if(A>=5) return true;if(B>=5) return false;if(edge==18) return A>B;for(int i=1;i<=18;i++)if(!edges[i]){edges[i]=true;  edge++;int nt=Num(); bool tmp;if(nt>A+B) tmp=MinSearch(A,nt-A);  //再走一次 else       tmp=MaxSearch(A,B);edges[i]=false; edge--;if(tmp==false) return false;}return true;
}
int find(int x,int y)
{for(int i=1;i<=18;i++)if(Edge[i][0]==x&&Edge[i][1]==y) return i;return -1;
}
int main()
{int T,kase=0,A,B; cin>>T;while(T--){int n,x,y; cin>>n;memset(edges,false,sizeof(edges));A=B=0; int next=1;               //1代表A for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);edges[find(x,y)]=true;int nt=Num();if(nt>A+B) next?A=nt-B:B=nt-A;else       next^=1;}edge=n;bool ans;if(next) ans=MaxSearch(A,B);else     ans=MinSearch(A,B);printf("Game %d: %c wins. \n",++kase,ans?'A':'B');}return 0;
}