hdu 1809 求SG函数
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; }
补充:软件开发 , C++ ,