本文主要是介绍CSP认证 201803-4 棋局评估(极大极小值搜索)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://118.190.20.162/view.page?gpid=T70
题目大意：给一个3*3棋盘，问按照最优策略下，如果1能赢输出赢后剩余未下的格子数+1,2能赢输出赢后负的剩下未下的格子数-1，平局输出0
题目思路：3*3很小，直接暴力所有情况，先手下尽可能想让值高，反手下尽可能想让值低，所以只用在所有可能中尽可能取利于自己的情况即可
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
int mp[5][5];
int solve(int p){int num=0;rep(i,1,3){rep(j,1,3){if(!mp[i][j])num++;}}if(p==1)return num+1;else return -num-1;
}
int check(){int num1=0,num2=0,p=0;rep(i,1,3){num1=0,num2=0;rep(j,1,3){if(mp[i][j]==1)num1++;if(mp[i][j]==2)num2++;}if(num1==3){p=1;break;}if(num2==3){p=2;break;}}if(p)return solve(p);rep(j,1,3){num1=0,num2=0;rep(i,1,3){if(mp[i][j]==1)num1++;if(mp[i][j]==2)num2++;}if(num1==3){p=1;break;}if(num2==3){p=2;break;}}if(p)return solve(p);num1=0,num2=0;rep(i,1,3){if(mp[i][i]==1)num1++;if(mp[i][i]==2)num2++;}if(num1==3)return solve(1);if(num2==3)return solve(2);num1=0,num2=0;rep(i,1,3){if(mp[i][4-i]==1)num1++;if(mp[i][4-i]==2)num2++;}if(num1==3)return solve(1);if(num2==3)return solve(2);int flag=0;rep(i,1,3){rep(j,1,3){if(!mp[i][j]){flag=1;break;}}if(flag)break;}if(!flag)return 0;return 1e9;
}
int dfs(int num){int rst;if(num==1)rst=-1e9;else rst=1e9;int flag=check();if(flag!=1e9)return flag;rep(i,1,3){rep(j,1,3){if(mp[i][j]==0){mp[i][j]=num;if(num==1)rst=max(rst,dfs(2));else rst=min(rst,dfs(1));mp[i][j]=0;}}}return rst;
}
int main()
{int t;scanf("%d",&t);while(t--){rep(i,1,3){rep(j,1,3){scanf("%d",&mp[i][j]);}}int ans=dfs(1);printf("%d\n",ans);}return 0;
}
这篇关于CSP认证 201803-4 棋局评估(极大极小值搜索)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
