首页 > 代码库 > 【poj1085】 Triangle War
【poj1085】 Triangle War
http://poj.org/problem?id=1085 (题目链接)
题意
A,B两人玩游戏，在一个大三角形上放火柴，若A放上一根火柴后成功组成一个三角形，那么这个三角形就归属于A，并且A被奖励再放一根火柴。最后谁三角形多谁就胜。
给出一个残局，判断是否存在先手必胜策略。
Solution
最近一直在颓，好久没刷题了。。。
这就是神乎其技的极大极小搜索，其实也差不多就是个贪心，基本很少用上，因为很难判断估价函数的正确性。。详情请见：http://blog.csdn.net/gwq5210/article/details/48163539。
极大极小搜索就是专门用来解决这一类问题的。在这道题中，我们先对于每一个火柴所放置的位置以及由3根火柴组成的三角形打一个表，将初始状态模拟出来。之后进行搜索，我们把 A的三角形个数-B的三角形个数 当做估价函数。而如果当前节点x与其父亲节点为同一个人决策时，x传承其父亲的alpha或者是beta。然后就是套模板了。
代码
// poj1085#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<queue>#define MOD 100003#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;/// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17int e[][2]={{1,2},{1,3},{2,4},{2,5},{2,3},{3,5},{3,6},{4,5},{4,7},{4,8},{5,6},{5,8},{5,9},{6,9},{6,10},{7,8},{8,9},{9,10}};int a[][3]={{0,1,4},{2,3,7},{3,4,5},{5,6,10},{8,9,15},{7,9,11},{11,12,16},{10,12,13},{13,14,17}};int n,cnt,f[20];int getid(int x,int y) { for (int i=0;i<18;i++) if ((e[i][0]==x && e[i][1]==y) || (e[i][0]==y && e[i][1]==x)) return i; return -1;}int cal() { int tt=0; for (int i=0;i<9;i++) if (f[a[i][0]] && f[a[i][1]] && f[a[i][2]]) tt++; return tt;}int maxdfs(int beta,int a,int b);int mindfs(int alpha,int a,int b) { if (cnt==18) return a>b ? inf : -inf; if (a>=5) return inf; if (b>=5) return -inf; int tmp=inf; for (int i=0;i<18;i++) if (!f[i]) { f[i]=1;cnt++; int c=cal(); if (c>a+b) tmp=min(mindfs(alpha,a,c-a),tmp); else tmp=min(maxdfs(tmp,a,b),tmp); f[i]=0;cnt--; if (tmp<=alpha) return tmp; } return tmp;}int maxdfs(int beta,int a,int b) { if (cnt==18) return a>b ? inf : -inf; if (a>=5) return inf; if (b>=5) return -inf; int tmp=-inf; for (int i=0;i<18;i++) if (!f[i]) { f[i]=1;cnt++; int c=cal(); if (c>a+b) tmp=max(maxdfs(beta,c-b,b),tmp); else tmp=max(mindfs(tmp,a,b),tmp); f[i]=0;cnt--; if (tmp>=beta) return tmp; } return tmp;}int main() { int T,t=0;scanf("%d",&T); while (T--) { scanf("%d",&n); memset(f,0,sizeof(f)); cnt=n; int w=0,ans[2]={0,0}; for (int x,y,i=1;i<=n;i++) { scanf("%d%d",&x,&y); int id=getid(x,y); f[id]=1; int c=cal(); if (c>ans[0]+ans[1]) ans[w]+=c-ans[0]-ans[1]; else w^=1; } int res=0; if (!w) res=maxdfs(inf,ans[0],ans[1]); else res=mindfs(-inf,ans[0],ans[1]); printf("Game %d: %c wins.\n",++t,res==inf ? ‘A‘ : ‘B‘); } return 0;}
【poj1085】 Triangle War
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。