hdu 1809 求SG函数

时间：2022-03-16 11:00:39

A New Tetris Game(2)

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 794    Accepted Submission(s): 275

Problem Description
自从Lele发明了新的类俄罗斯游戏 A New Tetris Game 后，他整日整夜得玩，现在渐渐的，他发现这个游戏也不过如此，为了加大点难度，他制定了一套新的规则：

首先，Lele和姐姐拿出N个长方形的棋盘，这些棋盘中有些格子是不可用的，剩下的都是可用的。每次Lele和姐姐轮流从N个棋盘里选出一个棋盘，拿出俄罗斯方块里的正方形方块(大小为2*2的正方形方块)往这个棋盘里放，要注意的是，放进去的正方形方块不能叠在棋盘不可用的格子上，也不能叠在已经放了的正方形方块上。

到最后，谁不能再放正方形方块，谁就输了。

现在，假设每次Lele和姐姐都很聪明，都能按最优策略放正方形，并且每次都是Lele先放正方形，你能告诉他他是否一定能赢姐姐吗？

 
Input
本题目包含多组测试，请处理到文件结束。

每组测试第一行包含一个正整数N(N<30)，表示棋盘的输个数

接下来有N个棋盘的描述。

对于每个棋盘，第一行有两个整数R,C(R*C<50),分别表示棋盘的行数和列数。然后有R行，每行C个字符来表示这个棋盘。

其中0是代表棋盘该位置可用，1是代表棋盘该位置不可用

你可以假设，每个棋盘中，0的个数不会超过40个。

 
Output
对于每一组测试，如果Lele有把握获胜的话，在一行里面输出"Yes"，否则输出"No"。

 
Sample Input
2
4 4
0000
0000
0000
0000
4 4
0000
0010
0100
0000
1
4 4
0000
0010
0100
0000
 
Sample Output
Yes
No
 
Author
linle
 
Source
 
思路：
根据求sg函数的模板找到模板的思想   套进本题 
#include<stdio.h>

#include<string.h>

#include<string>

#include<map>

using namespace std;

int n,m;

map<string,int>vis_str;

map<string,int>sg;

string s;

void add(int a[][50])//把矩阵转化为一个字符串

{

    int i,j;

    s="";

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

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

          s+=a[i][j]+'0';

}

int mex(int a[][50])

{

    int i,j,k;

    int vis_sg[100];//这里要搞成内置数组 不能搞成全局

    memset(vis_sg,0,sizeof(vis_sg));

    add(a);

    vis_str[s]=1;

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

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

        {

            if(a[i][j]==0&&a[i-1][j]==0&&a[i][j-1]==0&&a[i-1][j-1]==0)

            {

            a[i][j]=a[i-1][j]=a[i][j-1]=a[i-1][j-1]=1;

                add(a);

                if(vis_str[s])

                    k=sg[s];

                else

                    k=mex(a);

                vis_sg[k]=1;

            a[i][j]=a[i-1][j]=a[i][j-1]=a[i-1][j-1]=0;

            }

        }

        for(i=0;;i++)

        {

            if(!vis_sg[i]) {  add(a); sg[s]=i; return i;}

        }

}

int main()

{

    int i,j,a[50][50],t,ans;

    while(scanf("%d",&t)!=EOF)

     {

          ans=0;

         while(t--)

         {

            scanf("%d %d",&n,&m);

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

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

                scanf("%1d",&a[i][j]);

           // sg.clear();加上这2句就超时 好奇葩 求解答

           // vis_str.clear();

            ans=ans^mex(a);

        }

             if(ans) printf("Yes\n");

             else  printf("No\n");

     }

    return 0;

}

相关文章