暴搞SG的垃圾代码(不动脑筋引以为戒)
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
using namespace std;

map <string, int> sg;
map <string, bool> h;

int n, m;
char gra[51][51], str[2505];

 void out() {
 for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) printf("%c", gra[i][j]);
puts("");
}
puts("");
}

 void change() {
strcpy(str,"");
 for(int i = 0; i < n; i ++) {
strcat(str, gra[i]);
}
}

 inline bool can_set(int i, int j) {
if( gra[i][j] == '0' && gra[i+1][j] == '0' &&
 gra[i][j+1] == '0' && gra[i+1][j+1] == '0') {
gra[i][j] = '1'; gra[i+1][j] = '1';
gra[i][j+1] = '1'; gra[i+1][j+1] = '1';
return true;
}
return false;
}

 inline void unset(int i, int j) {
gra[i][j] = '0'; gra[i+1][j] = '0';
gra[i][j+1] = '0'; gra[i+1][j+1] = '0';
}


 int search() {
int num[12], tp;
memset(num, 0, sizeof(num));
change(); h[str] = 1;
 for(int i = 0; i < n - 1; i ++) {
 for(int j = 0; j < m - 1; j ++) {
 if( can_set(i, j) ) {
change();
if( h[str] )tp = sg[str];
else tp = search();
num[tp] = 1;
unset(i, j);
}
}
}
 for(int i = 0; i < 12; i ++) if( !num[i] ) {
change(); sg[str] = i;
return i;
}
}

 int main() {
h.clear(); sg.clear();
 while(scanf("%d %d", &n, &m) != EOF) {
 for(int i = 0; i < n; i ++) {
scanf("%s", gra[i]);
}
int ans = search();
if(!ans)puts("No");
else puts("Yes");
}
}

只考虑SG是否为0
#include <stdio.h>
#include <string.h>

int n, m;
char gra[51][51];

 inline bool can_set(int i, int j) {
if( gra[i][j] == '0' && gra[i+1][j] == '0' &&
 gra[i][j+1] == '0' && gra[i+1][j+1] == '0') {
gra[i][j] = '1'; gra[i+1][j] = '1';
gra[i][j+1] = '1'; gra[i+1][j+1] = '1';
return true;
}
return false;
}

 inline void unset(int i, int j) {
gra[i][j] = '0'; gra[i+1][j] = '0';
gra[i][j+1] = '0'; gra[i+1][j+1] = '0';
}


 int search() {
int flag = 0;
 for(int i = 0; i < n - 1; i ++) {
 for(int j = 0; j < m - 1; j ++) {
 if( can_set(i, j) ) {
flag ++;
 if( search() == 0) {
unset(i, j);
return 1;
}
unset(i,j);
}
}
}
if(flag<=1) return flag;
return 0;
}

 int main() {
 while(scanf("%d %d", &n, &m) != EOF) {
 for(int i = 0; i < n; i ++) {
scanf("%s", gra[i]);
}
int ans = search();
if(!ans)puts("No");
else puts("Yes");
}
}

|