题目链接：
?pid=1760
题目大意：
给你一个N*M的矩阵棋盘。数字0代表该位置可用，数字1代表该位置不可以。Lele和姐姐在这个
棋盘上下棋，每次在棋盘上放一个大小为2*2的正方形，棋子间不能相互叠加。两个人轮流放，每
次都按最优策略放正方形。轮到谁没有地方放置棋子了，，就算谁输。若每次都是Lele先放，那么问
题来了：Lele是否一定能赢姐姐呢。
思路：
博弈中的必胜态：当前所能到达的状态能到达一个必败态，则当前状态为必胜态。
博弈中的必败态：若当前状态到达的所有状态都是必胜态，则当前状态为必败态。
这道题和简单的取石子游戏差不多。就是DFS搜索SG值。根据题目大意可得：不能再放为必败态。
刚开始的时候，初始状态为整个棋盘，设为A。搜索位置去放置一个正方形之后的状态设为B。判断
状态B是否必败，如果必败，则状态A就是必胜态。如果状态A所有可以走到的状态B都为必胜态，那
么状态A为必败态，如果状态A无路可走也是必败态。当我们到达必胜点时，就要转换当前状态继续
递归查找SG值。递归返回0必败，返回1必胜。搜索状态B的时候，一定要注意搜索完后记得还原状态。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;char Map[55][55];int DFS(int N,int M){for(int i = 0; i < N-1; ++i){for(int j = 0; j < M-1; ++j){if(Map[i][j]=='0' && Map[i+1][j]=='0' && Map[i][j+1]=='0' && Map[i+1][j+1]=='0'){Map[i][j] = Map[i+1][j] = Map[i][j+1] = Map[i+1][j+1] = '1';if(!DFS(N,M)){Map[i][j] = Map[i+1][j] = Map[i][j+1] = Map[i+1][j+1] = '0';return 1;}Map[i][j] = Map[i+1][j] = Map[i][j+1] = Map[i+1][j+1] = '0';}}}return 0; //最终没有可放为必败局}int main(){int N,M;while(cin >> N >> M){for(int i = 0; i < N; ++i)cin >> Map[i];if(DFS(N,M))cout << "Yes" << endl;elsecout << "No" << endl;}return 0;}
阳光总在风雨后。只有坚强的忍耐顽强的奋斗，
