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 HDOJ 2007 Summer Exercise（2） 思路： 根據求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;
}
