原题链接:CCF-CSP 201803-4 棋局评估
推荐博客:CSP认证:棋局评估
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f;
int a[3][3];
bool check(int w)
{
for(int i=0;i<3;i++)
{
int res=0;
for(int j=0;j<3;j++)
{
if(a[i][j]==w) res++;
}
if(res==3) return true;
}
for(int j=0;j<3;j++)
{
int res=0;
for(int i=0;i<3;i++)
{
if(a[i][j]==w) res++;
}
if(res==3) return true;
}
if(a[0][0]==w && a[1][1]==w && a[2][2]==w ) return true;
if(a[0][2]==w && a[1][1]==w && a[2][0]==w ) return true;
return false;
}
int eval()
{
int res=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(a[i][j]==0) res++;
}
}
if(check(1)) return res+1;
else if(check(2)) return -(res+1);
else if(res==0) return 0;
return INF;
}
int dfs(int w)
{
int tmp=eval();
if(tmp!=INF) return tmp;
if(w==1)
{
int res=-INF;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(a[i][j]==0)
{
a[i][j]=1;
res=max(res,dfs(2));
a[i][j]=0;
}
}
}
return res;
}
else
{
int res=INF;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(a[i][j]==0)
{
a[i][j]=2;
res=min(res,dfs(1));
a[i][j]=0;
}
}
}
return res;
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cin>>a[i][j];
}
}
cout<<dfs(1)<<endl;
}
return 0;
}