【胡搞的不能AC的题解，暴力搜索一发博弈问题】1995 三子棋

1995 三子棋

题目来源： syu校赛

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

原题链接： https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1995

小的时候大家一定玩过“井”字棋吧。也就是在九宫格中，只要任意行、列，或者任意连续对角线上面出现三个相同的，就能获胜。现在小明和小花也在玩三子棋，但是他们不是在九宫格里，而是在3×4的格子里面。现在小明先下，但是他知道小花这个人很聪明，他想知道第一步下在哪一个地方最合适，你能帮帮他吗？

Input

第一行输入一个整数T，表示数据组数（1<T<10000）； 

第二行输入两个整数x,y,表示3×4格子里面的一个坐标(x,y)（1<=x<=3,1<=y<=4）；

Output

每组数据输出最后小明输赢的结果，如果小明一定能赢，第一行输出“Win”,第二行输出小明所需要花的最少步数；如果小明跟小花只能打成平手，第一行输出“Equal”，第二行输出数字0；如果小明不能赢也不能跟小花打成平手，第一行输出“Lose”,第二行输出小花赢小明所需要花的最少步数。

Input示例

Output示例

Equal

0

Equal

0

-------------------------------------------------------------------------------
看到这个题目我想到了搜索，但计算了一下时间复杂度：不是很大，应该不会超时！但是，这是个博弈问题，暴力穷举的话没法进行模拟！

 #include<stdio.h>

 #include<string.h>

 #include<iostream>

 #include<stdlib.h>

 #include<math.h>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define inf 0x3f3f3f3f

 #define emin 1e-10

 #define ll long long   //10:19--

 int mp[][],flag;

 int dir[][]= { {,},{,-},{,},{,-},{,},{-,-},{-,},{-,} };

 int check()

 {

     int i,j;

     for(j=; j<=; j++) //竖行

     {

         if(mp[][j]==mp[][j]&&mp[][j]==mp[][j]&&mp[][j]!=-)

             return mp[][j];

     }

     for(i=; i<=; i++) //横行

     {

         if(mp[i][]==mp[i][]&&mp[i][]==mp[i][]&&mp[i][]!=-)

             return mp[i][];

         if(mp[i][]==mp[i][]&&mp[i][]==mp[i][]&&mp[i][]!=-)

             return mp[i][];

     }

     if(mp[][]==mp[][]&&mp[][]==mp[][]&&mp[][]!=-)

         return mp[][];

     if(mp[][]==mp[][]&&mp[][]==mp[][]&&mp[][]!=-)

         return mp[][];

     if(mp[][]==mp[][]&&mp[][]==mp[][]&&mp[][]!=-)

         return mp[][];

     if(mp[][]==mp[][]&&mp[][]==mp[][]&&mp[][]!=-)

         return mp[][];

     return -; //当前局面无结果

 }

 void print_mp()

 {

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

     {

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

             printf("%3d",mp[i][j]);

         printf("\n");

     }

 }

             //num=0表示先手下棋者，num=1表示后手下棋者

 int game(int step,int num) //当前正要走的的步数step,num表示当前step步下棋者

 {

     int i,j,k;

     if(step==) //至多12个格子

         return -;

     if(k=check(),k!=-) //不用下棋时就已经达到获胜或者失败的局面了！

     {

         return k;

     }

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

     {

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

         {

             if(mp[i][j]==-)

             {

                 mp[i][j]=num;

                 if(check()==num) //下完一步后,检验整个棋盘可以获胜则返回

                 {

                     mp[i][j]=-;

                     return num;  //返回当前局面的获胜者

                 }

                 if(game(step+,!num)==num) //后续递归博弈处理可以胜利则返回

                 {

                     mp[i][j]=-;

                     return num;  //返回当前局面的获胜者

                 }

                 mp[i][j]=-;

             }

         }

     }

     return !num;

 }

 int main()

 {

     int a,b,ans;

     // init();

     for(a=; a<=; a++)

     {

         for(b=; b<=; b++)

         {

             memset(mp,-,sizeof(mp));

             mp[a][b]=;//先手先下一步

             ans=game(,);  //调用博弈函数

             if(ans==)

                 printf("当a=%d，b=%d, 先手Win\n",a,b);

             else

                 printf("当a=%d，b=%d, 先手Lose 或者 Equal\n",a,b);

         }

     }

     return ;

 }

友情提示这不是题解！没法判断是否可以达到平局的局面，但这题不存在平局的局面；想判断的话，可以用调用game函数的次数来判断！（可能吧！）

像这类博弈问题基本都是找规律的，找不出来规律就没法了！除非很水的题！

巴特西

【胡搞的不能AC的题解，暴力搜索一发博弈问题】1995 三子棋 - 51Nod

最新文章

热门文章