暴搞SG的垃圾代碼（不動(dòng)腦筋引以為戒）
 #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");
}
}
|