首页 > 代码库 > 【poj1568】 Find the Winning Move

【poj1568】 Find the Winning Move

http://poj.org/problem?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