Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
照着维基百科的模板敲的alphabeta,比较精炼~ 219ms水过~#include <cstdio> #include <algorithm> using namespace std; const int full=(1<<18)-1; int mat[11][11]={{0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,1,0,0,0,0,0,0,0}, {0,0,0,2,3,4,0,0,0,0,0}, {0,1,2,0,0,5,6,0,0,0,0}, {0,0,3,0,0,7,0,9,10,0,0}, {0,0,4,5,7,0,8,0,11,12,0}, {0,0,0,6,0,8,0,0,0,13,14}, {0,0,0,0,9,0,0,0,15,0,0}, {0,0,0,0,10,11,0,15,0,16,0}, {0,0,0,0,0,12,13,0,16,0,17}, {0,0,0,0,0,0,14,0,0,17,0} }; int triangle[9]={7,152,52,352,34304,3200,71680,12544,155648}; int nxt_state(int cur,int seg,int &cnt_a,int &cnt_b,bool flag) { int ret=cur|seg; for (int i = 0; i < 9; i++) { if ((cur&triangle[i])!=triangle[i]&&(ret&triangle[i])==triangle[i]) { if (flag) cnt_a++; else cnt_b++; } } return ret; } int alpha_beta(int cur,int alpha,int beta,bool flag,int cnt_a,int cnt_b) { if (cnt_a>=5) return 1; if (cnt_b>=5) return -1; if (cur==full) return cnt_a>cnt_b?1:-1; int remain=~cur&full; int t_cnt_a=cnt_a,t_cnt_b=cnt_b; if (flag) { while (remain) { cnt_a=t_cnt_a; int seg=remain&(-remain),tmp=cnt_a; remain-=seg; int nxt=nxt_state(cur,seg,cnt_a,cnt_b,true); if (cnt_a>tmp) alpha=max(alpha,alpha_beta(nxt,alpha,beta,true,cnt_a,cnt_b)); else alpha=max(alpha,alpha_beta(nxt,alpha,beta,false,cnt_a,cnt_b)); if (alpha>=beta) break; } return alpha; } else { while (remain) { cnt_b=t_cnt_b; int seg=remain&(-remain),tmp=cnt_b; remain-=seg; int nxt=nxt_state(cur,seg,cnt_a,cnt_b,false); if (cnt_b>tmp) beta=min(beta,alpha_beta(nxt,alpha,beta,false,cnt_a,cnt_b)); else beta=min(beta,alpha_beta(nxt,alpha,beta,true,cnt_a,cnt_b)); if (alpha>=beta) break; } return beta; } } int main() { int kase; scanf("%d",&kase); for (int t=1;t<=kase;t++) { int n,i,j,cnt_a=0,cnt_b=0,cur=0; bool flag=true; scanf("%d",&n); while (n--) { scanf("%d%d",&i,&j); int tmp_a=cnt_a,tmp_b=cnt_b; cur=nxt_state(cur,1<<mat[i][j],cnt_a,cnt_b,flag); if (cnt_a==tmp_a&&cnt_b==tmp_b) flag=!flag; } char winner=~alpha_beta(cur,-1,1,flag,cnt_a,cnt_b)?'A':'B'; printf("Game %d: %c wins.\n",t,winner); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator