学步园

　　用dfs搜索每种情况所对应的sg值（这里也就是对应的是N位还是P位），若下一步为P位，则当前一步为N位。。。

代码：

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 55;

char map[N][N];
int m, n;

int judge(int i, int j){
if(map[i][j] == '0' && map[i][j+1] == '0' && map[i+1][j] == '0' && map[i+1][j+1] == '0'){
        map[i][j] = map[i][j+1] = map[i+1][j] = map[i+1][j+1] = '1';
return 1;
    }
return 0;
}

void recover(int i, int j){
    map[i][j] = map[i][j+1] = map[i+1][j] = map[i+1][j+1] = '0';
}

int dfs(){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(judge(i, j)){
if(!dfs()){
                    recover(i, j);
return 1;
                }
                recover(i, j);
            }
        }
    }
return 0;
}

int main(){
    freopen("data.in", "r", stdin);

while(~scanf("%d%d", &n, &m)){
        getchar();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
                scanf("%c", &map[i][j]);
            }
            getchar();
        }
if(dfs())    puts("Yes");
else    puts("No");
    }
return 0;
}