?id=1568 (题目链接)
题意两人下4*4的井字棋，，给出一个残局，问是否有先手必胜策略。
Solution极大极小搜索。。
这里有个强力优化，若已经被下了的的格子数cnt小于等于4的话，那么一定是平局至于为什么，自己YY一下发现好像是这样的。。
代码// poj1568 #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; char s[4][4]; int a[4][4],cnt; int check(int f,int &X,int &Y) { for (int i=0;i<4;i++) { int ff=0; for (int j=0;j<4;j++) if (a[i][j]==f) ff++; //if (ff==3) for (int j=0;j<4;j++) if (!a[i][j]) {X=i,Y=j;return 1;} if (ff==4) return 1; } for (int j=0;j<4;j++) { int ff=0; for (int i=0;i<4;i++) if (a[i][j]==f) ff++; //if (ff==3) for (int i=0;i<4;i++) if (!a[i][j]) {X=i,Y=j;return 1;} if (ff==4) return 1; } int ff=0; for (int i=0;i<4;i++) if (a[i][i]==f) ff++; //if (ff==3) for (int i=0;i<4;i++) if (!a[i][i]) {X=i,Y=i;return 1;} if (ff==4) return 1; ff=0; for (int i=0;i<4;i++) if (a[i][4-i-1]==f) ff++; //if (ff==3) for (int i=0;i<4;i++) if (!a[i][4-i-1]) {X=i,Y=4-i-1;return 1;} if (ff==4) return 1; return 0; } int maxdfs(int beta,int &X,int &Y); int mindfs(int alpha,int &X,int &Y) { if (cnt==16) return 0; int x,y,tmp=inf; int f=check(1,X,Y); if (f==1) return inf; for (int i=0;i<4;i++) for (int j=0;j<4;j++) if (!a[i][j]) { X=i,Y=j;a[i][j]=2;cnt++; tmp=min(tmp,maxdfs(tmp,x,y)); a[i][j]=0;cnt--; if (tmp<=alpha) return tmp; } return tmp; } int maxdfs(int beta,int &X,int &Y) { if (cnt==16) return 0; int x,y,tmp=-inf; int f=check(2,X,Y); if (f==1) return -inf; for (int i=0;i<4;i++) for (int j=0;j<4;j++) if (!a[i][j]) { X=i,Y=j;a[i][j]=1;cnt++; tmp=max(tmp,mindfs(tmp,x,y)); a[i][j]=0;cnt--; if (tmp>=beta) return tmp; } return tmp; } int main() { while (scanf("%s",s[0]) && s[0][0]!=‘$‘) { cnt=0; for (int i=0;i<4;i++) scanf("%s",s[i]); for (int i=0;i<4;i++) for (int j=0;j<4;j++) { if (s[i][j]==‘.‘) a[i][j]=0; else if (s[i][j]==‘x‘) a[i][j]=1; else if (s[i][j]==‘o‘) a[i][j]=2; if (s[i][j]!=‘.‘) cnt++; } if (cnt<=4) {printf("#####\n");continue;} //蜜汁优化 int X,Y; int res=maxdfs(inf,X,Y); if (res==inf) printf("(%d,%d)\n",X,Y); else printf("#####\n"); } return 0; }
【poj1568】 Find the Winning Move