CCF201803-4棋局评估（博弈，极大极小值搜索，alpha_beta剪枝）

剪枝的状况c++

#include<bits/stdc++.h>
using namespace std;
const int maxn  = 1e5+10;
int N;
int a[4][4];
int alpha_beta(int turn,int alpha,int beta);
int check();
int main(){
	int alpha,beta;
	cin>>N;
	while(N--){
		for(int i=1;i<=3;i++){
			for(int j=1;j<=3;j++){
				cin>>a[i][j];
			}
		}
		alpha = -100;
		beta = 100;
		cout<<alpha_beta(1,alpha,beta)<<endl;
	}
	return 0;
}
int alpha_beta(int turn,int alpha,int beta)
{
	int re = check();
	if(re!=100){
		return re;
	} 
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(a[i][j] == 0){//有位置 
				a[i][j] = turn;
				if(turn == 1){//在max层 
					re = alpha_beta(2,alpha,beta);
					a[i][j] = 0;
					if(re>alpha){
						alpha = re;
					}
					if(alpha >= beta){
						return alpha;
					}
				}else{
					re = alpha_beta(1,alpha,beta);
					a[i][j] = 0;
					if(re<beta){
						beta = re;
					}
					if(alpha>= beta){
						return beta;
					}
				} 
			}
		}
	}
	if(turn == 1){
		return alpha;
	}else{
		return beta;
	}
} 
int check()
{
	int flag = 0;
	for(int i=1;i<=3;i++){
		//行
		if((a[i][1]!=0)&&(a[i][1] == a[i][2])&&(a[i][2] == a[i][3])){
			flag = a[i][1];
			break;
		} 
		//列 
		if((a[1][i]!=0)&&(a[1][i]==a[2][i])&&(a[2][i]==a[3][i])){
			flag = a[1][i];
			break;
		}
	}
	if(flag == 0){//尚未找到一行一列 开始找对角线 
		if((a[1][1]!=0)&&(a[1][1]==a[2][2])&&(a[2][2]==a[3][3])){
			flag = a[1][1];
		}
		if((a[3][1]!=0)&&(a[3][1]==a[2][2])&&(a[2][2]==a[1][3])){
			flag = a[3][1];
		}	
	} 
	int score = 0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(a[i][j] == 0){
				score++;
			}
		}
	}
	if(flag){//若是有人赢了  
		if(flag == 1) return score+1;
		if(flag == 2) return (-1)*(score+1);
	}else{//若是没有人赢  
		if(score == 0){//说明棋局满了 
			return 0;
		}else{//尚未分出来胜负 
			return 100;
		}
	}
}

没有剪枝的状况spa

//没有剪枝的状况
#include<bits/stdc++.h>
using namespace std;
const int maxn  = 1e5+10;
int N;
int a[4][4];
int a_b(int turn);
int check();

int main(){
	cin>>N;
	while(N--){
		for(int i=1;i<=3;i++){
			for(int j=1;j<=3;j++){
				cin>>a[i][j];
			}
		}
		cout<<a_b(1)<<endl;
	}
	return 0;
}
int a_b(int turn)
{
	int re = check();
	if(re != 100){//若是说返回的不是100 那就说明分出来胜负了 
		return re;
	}	
	//若是尚未分出来 那么就须要下棋了
	if(turn == 1){
		re = -100;//要找最大的 
	}else{
		re = 100;//要找最小的 
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(a[i][j] == 0){
				a[i][j] = turn;
				if(turn == 1){
					re = max(re,a_b(2)); 
				}else{
					re = min(re,a_b(1));
				}
				a[i][j] = 0;
			}
		}
	} 
	return re;
} 
int check()
{
	int flag = 0;
	for(int i=1;i<=3;i++){
		//行
		if((a[i][1]!=0)&&(a[i][1] == a[i][2])&&(a[i][2] == a[i][3])){
			flag = a[i][1];
			break;
		} 
		//列 
		if((a[1][i]!=0)&&(a[1][i]==a[2][i])&&(a[2][i]==a[3][i])){
			flag = a[1][i];
			break;
		}
	}
	if(flag == 0){//尚未找到一行一列 开始找对角线 
		if((a[1][1]!=0)&&(a[1][1]==a[2][2])&&(a[2][2]==a[3][3])){
			flag = a[1][1];
		}
		if((a[3][1]!=0)&&(a[3][1]==a[2][2])&&(a[2][2]==a[1][3])){
			flag = a[3][1];
		}	
	} 
	int score = 0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(a[i][j] == 0){
				score++;
			}
		}
	}
	if(flag){//若是有人赢了  
		if(flag == 1) return score+1;
		if(flag == 2) return (-1)*(score+1);
	}else{//若是没有人赢  
		if(score == 0){//说明棋局满了 
			return 0;
		}else{//尚未分出来胜负 
			return 100;
		}
	}
}