题目连接:http://118.190.20.162/view.page?gpid=T70c++
题目大意:给一个3*3棋盘,问按照最优策略下,若是1能赢输出赢后剩余未下的格子数+1,2能赢输出赢后负的剩下未下的格子数-1,平局输出0spa
题目思路:3*3很小,直接暴力全部状况,先手下尽量想让值高,反手下尽量想让值低,因此只用在全部可能中尽量取利于本身的状况便可code
如下是代码:
get
#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; }