201803-4 棋牌评估

思路

讲真的有限的东西直接暴力枚举就完事了，自己还是想太多了，这种题目应该是要拿下的。当时自己题目的意思也没理解，不应该。

代码

#include 
#include 
using namespace std;
int g[3][3];
int zeronum(){
	int cnt = 0;
	for(int i = 0;i<3;i++){
		for(int j = 0;j<3;j++){
			if(g[i][j] == 0)cnt++;
		}
	} 
	return cnt;
}
bool check(int x){
	for(int i = 0;i<3;i++){
		int s = 0;
		for(int j = 0;j<3;j++){
			if(g[i][j] == x){
				s++;
			}
		}
		if(s == 3){
			return true;
		}
		s = 0;
		for(int j = 0;j<3;j++){
			if(g[j][i] == x){
				s++;
			}
		}
		if(s == 3){
			return true;
		}
	}
	if(g[0][0] == x && g[1][1] == x && g[2][2] == x){
		return true;
	}
	if(g[2][0] == x && g[1][1] == x && g[0][2] == x){
		return true;
	}
	return false;
}
int dfs(int x){
	int s = zeronum();
	if(check(1)){
			//如果Alice已经赢了
		return s + 1; 
	}
	if(check(2)){
			//如果Bob已经赢了
		return -(s + 1); 
	}
	if(s == 0){
		return 0;
	}
	if(s == 9){
		return 0;
	}
	if(x){//1表示Bob 
		int res = INT_MAX;
		for(int i = 0;i<3;i++){
			for(int j = 0;j<3;j++){
				if(!g[i][j]){
					g[i][j] = 2;
					res = min(res, dfs(0));
					g[i][j] = 0;
				}
			}
		}
		return res;
	}else{//0表示Alice 
		int res = INT_MIN;
		//如果自己还可以下，就dfs枚举每种状态 
		for(int i = 0;i<3;i++){
			for(int j = 0;j<3;j++){
				if(!g[i][j]){
					g[i][j] = 1;
					res = max(res, dfs(1));
					g[i][j] = 0;
				}
			}
		}
		return res;
	} 
}
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		for(int i = 0;i<3;i++){
			for(int j = 0;j<3;j++){
				scanf("%d", &g[i][j]);
			}
		}
		cout<