首页 > 代码库 > 哈理工OJ P2320：OX

哈理工OJ P2320：OX

2024-08-27 15:21:06   218人阅读

题目链接：OX

 

题意 ：给出一个3X3的黑白棋棋盘，棋盘上有若干黑白子，再给出下一个下的人，问下一个下的人能否赢

 

分析：考虑到只有39种状态，故用一个数保存目前棋盘的状态，记为value，再枚举空位DFS，每次

DFS先判该状态是否已到达（剪枝），再拆分状态用c[3][3]储存，判断是否有赢的状态，最后遍历

棋盘寻找空位，若有则下，value储存状态，再DFS下去，注意返回c[i][j]清零

判断胜负平的条件如下：

　　若有一个状态可以到达必败点，则该点必胜，返回1

　　若有一个状态可以到达平局点，则该点平局，返回-1

　　否则必败，返回0

详情见代码

 

技术分享
 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1e5+10; 6 int t,dp[maxn][3],st; 7 char s[3]; 8  9 int dfs(int value,int st)10 {11     if(dp[value][st]!=-2) return dp[value][st];12     int c[3][3],sum=0,n1=0,n2=0;//memset(c,0,sizeof(c));13     for(int i=0;i<3;++i)for(int j=0;j<3;++j)14     {15         c[i][j]=value%3;value/=3;16         if(c[i][j]) sum++;17     }18     for(int i=0;i<3;++i)19     {20         if(c[i][0]==c[i][1]&&c[i][1]==c[i][2]) if(c[i][0]==1) n1=1;else if(c[i][0]==2) n2=1;21         if(c[0][i]==c[1][i]&&c[1][i]==c[2][i]) if(c[0][i]==1) n1=1;else if(c[0][i]==2) n2=1;22     }23     if(c[0][0]==c[1][1]&&c[1][1]==c[2][2]) if(c[1][1]==1) n1=1;else if(c[1][1]==2) n2=1;24     if(c[0][2]==c[1][1]&&c[1][1]==c[2][0]) if(c[1][1]==1) n1=1;else if(c[1][1]==2) n2=1;25     if(n1&&st==1) return 1;26     if(n2&&st==1) return 0;27     if(n1&&st==2) return 0;28     if(n2&&st==2) return 1;29     if(sum==9) return -1;30     int judge=0;31     for(int i=0;i<3;++i)for(int j=0;j<3;++j) if(c[i][j]) continue;32     else33     {34         int value=http://www.mamicode.com/0;35         c[i][j]=st;36         for(int p=0;p<3;++p)for(int k=0;k<3;++k) value=http://www.mamicode.com/value*3+c[p][k];37         c[i][j]=0;//很重要，返回时清038         int ans=dfs(value,3-st);39         if(ans==0) return 1;//可以到达必败点的为必胜点40         if(ans==-1) judge=1;//可以到达平局的状态返回平局41     }42     if(judge) return -1;else return 0;//否则返回必败点43 }44 int main()45 {46     for(scanf("%d",&t);t--;)47     {48         for(int i=0;i<maxn;++i)for(int j=0;j<3;++j) dp[i][j]=-2;49         int value=http://www.mamicode.com/0;50         for(int i=0;i<3;++i)for(int j=0;j<3;++j)51         {52             scanf("%s",s);53             if(s[0]==‘o‘) value=http://www.mamicode.com/value*3+2;54             else if(s[0]==‘x‘) value=http://www.mamicode.com/value*3+1;55             else value=http://www.mamicode.com/value*3;56         }57         scanf("%s",s);58         if(s[0]==‘x‘) st=1;else st=2;59         int ans=dfs(value,st);60         if(ans==0) printf("%c win!\n",st==1?‘o‘:‘x‘);61         else if(ans==1) printf("%c win!\n",st==2?‘o‘:‘x‘);62         else puts("tie!");63     }64 }
View Code

 

哈理工OJ P2320：OX


联系
我们