首先分析,题目给出的是一个棋盘,让咱们计算轮到1下时,当前局面的得分是多少。两人都以最优策略行棋。显然这是一个对抗搜索的问题,须要用到极大极小算法,因为数据量较小,不须要用到alpha-beta剪枝。ios
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int T; int c[4][4]={0}; bool judge(int x){ //判断当前状况是否第x人已获胜 for(int i=1;i<=3;i++){ if(c[i][1]==c[i][2]&&c[i][1]==c[i][3]&&c[i][1]==x) return true; } for(int j=1;j<=3;j++){ if(c[1][j]==c[2][j]&&c[1][j]==c[3][j]&&c[1][j]==x) return true; } if(c[1][1]==c[2][2]&&c[1][1]==c[3][3]&&c[1][1]==x) return true; if(c[1][3]==c[2][2]&&c[1][3]==c[3][1]&&c[1][3]==x) return true; return false; } int goal(int x){ //判断第x我的赢的状况下,他的得分是多少 int ans=1; for(int i=1;i<=3;i++){ for(int j=1;j<=3;j++) if(c[i][j]==0) ans++; } if(x==1) return ans; return -ans; } int dfs(int x){ if(goal(1)==1) return 0; //若已无子可下,平局 int MAX=-1<<30; int MIN=1<<30; for(int i=1;i<=3;i++){ for(int j=1;j<=3;j++){ if(c[i][j]) continue; c[i][j]=x; if(judge(x)){ //若第x人在该局已经获胜 if(x==1) MAX=max(MAX,goal(1)); //将当前局面和已知的最优解比较,取较大值 else MIN=min(MIN,goal(2)); } else{ //若第x人该步未获胜 if(x==1) MAX=max(MAX,dfs(2)); //将将来局面和已知的最优解比较,取较大值 else MIN=min(MIN,dfs(1)); } c[i][j]=0; //回溯 } } if(x==1) return MAX; //若这一步是x走的,返回他在最优状况下的得分 return MIN; } int main(){ scanf("%d",&T); while(T--){ for(int i=1;i<=3;i++){ for(int j=1;j<=3;j++){ scanf("%d",&c[i][j]); } } if(judge(1)) printf("%d\n",goal(1)); //若该局面1已获胜 else if(judge(2)) printf("%d\n",goal(2)); //若该局面2已获胜 else printf("%d\n",dfs(1)); //第1人以最优步骤下棋 } return 0; }