POJ1568_Find the Winning Move(α-β剪枝)

题意：

相当于四子棋，给出一个4x4的棋局的局面，问先手 “x” 是不是能找在接下来的一步中

找到一个必胜局面，如果有，输出 ‘x’ 下一步下子的坐标（行列都由 0 开始）；否则输出字符串 “#####”。

思路：

参看了这里的代码
第一次写博弈，看看别人的写法，先模仿，实践一下~

#include <cstdio>
using namespace std;
char G[5][5];
int tot_step;	// 双方总步数
int ansx, ansy; 

int alpha(int x, int y);
int beta(int x, int y);
int check_over();

// 模拟 x 
int alpha(int x, int y){
	if(check_over()) return -1;		// 已经结束, 对方胜 
	if(tot_step == 16) return 0;
	for(int i = 0; i < 4; ++i){
		for(int j = 0; j < 4; ++j) if(G[i][j] == '.'){
			G[i][j] = 'x';
			++tot_step;
			int ans = beta(i, j);
			G[i][j] = '.';
			--tot_step;
			if(ans == 1) return 1;
		}
	}
	return -1;
}

// 模拟 o 
int beta(int x, int y){
	if(check_over()) return 1;	// 已经结束, 我方胜 
	if(tot_step == 16) return 0;
	for(int i = 0; i < 4; ++i){
		for(int j = 0; j < 4; ++j) if(G[i][j] == '.'){
			G[i][j] = 'o';
			++tot_step;
			int ans = alpha(i, j);
			G[i][j] = '.';
			--tot_step;
			if(ans == 0||ans == -1) return -1;	// 只要存在一种走法使得不能稳赢即可 
		}
	}
	return 1;
}

// 检查是否有一方获胜 
int check_over(){
	int xa = 0, ya = 0, la = 0, ra = 0;		// 横, 纵, 两条对角线 
	int xb = 0, yb = 0, lb = 0, rb = 0;
	for(int i = 0; i < 4; ++i){
		// 检查第i行和第i列 
		xa = ya = 0;
		xb = yb = 0;
		for(int j = 0; j < 4; ++j){
			if(G[i][j] == 'x') ++xa;
			else if(G[i][j] == 'o') ++xb;
			if(G[j][i] == 'x') ++ya;
			else if(G[j][i] == 'o') ++yb;
		}
		// 累加统计对角线 
		if(G[i][i] == 'x') ++ra;
		else if(G[i][i] == 'o') ++rb;
		if(G[i][3-i] == 'x') ++la;
		else if(G[i][3-i] == 'o') ++lb;
		// 判断 
		if(xa == 4||ya == 4||xb == 4||yb == 4||la == 4||lb == 4||ra == 4||rb == 4)
			return 1;
	}
	return 0;
}

int found(){
	for(int i = 0; i < 4; ++i){
		for(int j = 0; j < 4; ++j) if(G[i][j] == '.'){
			G[i][j] = 'x';	// 试着走一步
			++tot_step;
			int ans = beta(i, j);
			G[i][j] = '.';	// 回溯 
			--tot_step;
			if(1 == ans){
				ansx = i; ansy = j;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	char str[5];
	while(scanf("%s",str) == 1){
		if(str[0] == '$') break;
		tot_step = 0;
		for(int i = 0; i < 4; ++i){
			scanf("%s", G[i]);
			for(int j = 0; j < 4; ++j) if(G[i][j] != '.') ++tot_step;
		}
		// 不加这个剪枝直接超时 ! 
		if(tot_step <= 4){
			printf("#####\n");
			continue;
		}
		if(found()) printf("(%d,%d)\n",ansx,ansy);
		else printf("#####\n");
	}
	fclose(stdin);
	return 0;
}