哈理工OJ P2320：OX

题目链接：OX

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

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

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

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

判断胜负平的条件如下：

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

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

　　否则必败，返回0

详情见代码

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=1e5+;

 int t,dp[maxn][],st;

 char s[];

 int dfs(int value,int st)

 {

     if(dp[value][st]!=-) return dp[value][st];

     int c[][],sum=,n1=,n2=;//memset(c,0,sizeof(c));

     for(int i=;i<;++i)for(int j=;j<;++j)

     {

         c[i][j]=value%;value/=;

         if(c[i][j]) sum++;

     }

     for(int i=;i<;++i)

     {

         if(c[i][]==c[i][]&&c[i][]==c[i][]) if(c[i][]==) n1=;else if(c[i][]==) n2=;

         if(c[][i]==c[][i]&&c[][i]==c[][i]) if(c[][i]==) n1=;else if(c[][i]==) n2=;

     }

     if(c[][]==c[][]&&c[][]==c[][]) if(c[][]==) n1=;else if(c[][]==) n2=;

     if(c[][]==c[][]&&c[][]==c[][]) if(c[][]==) n1=;else if(c[][]==) n2=;

     if(n1&&st==) return ;

     if(n2&&st==) return ;

     if(n1&&st==) return ;

     if(n2&&st==) return ;

     if(sum==) return -;

     int judge=;

     for(int i=;i<;++i)for(int j=;j<;++j) if(c[i][j]) continue;

     else

     {

         int value=;

         c[i][j]=st;

         for(int p=;p<;++p)for(int k=;k<;++k) value=value*+c[p][k];

         c[i][j]=;//很重要，返回时清0

         int ans=dfs(value,-st);

         if(ans==) return ;//可以到达必败点的为必胜点

         if(ans==-) judge=;//可以到达平局的状态返回平局

     }

     if(judge) return -;else return ;//否则返回必败点

 }

 int main()

 {

     for(scanf("%d",&t);t--;)

     {

         for(int i=;i<maxn;++i)for(int j=;j<;++j) dp[i][j]=-;

         int value=;

         for(int i=;i<;++i)for(int j=;j<;++j)

         {

             scanf("%s",s);

             if(s[]=='o') value=value*+;

             else if(s[]=='x') value=value*+;

             else value=value*;

         }

         scanf("%s",s);

         if(s[]=='x') st=;else st=;

         int ans=dfs(value,st);

         if(ans==) printf("%c win!\n",st==?'o':'x');

         else if(ans==) printf("%c win!\n",st==?'o':'x');

         else puts("tie!");

     }

 }

巴特西

哈理工OJ P2320：OX

最新文章

热门文章