a new tetris game(2)(博弈sg).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int n,r,c;
char game[55][55];
map<string, char> sg;

inline string make_hash()
{
	int i,j;
	string state = "";
	for (i=0;i<r;i++) {
		for (j=0;j<c;j++) {
			state += (game[i][j] - '0') + ('A' + 2*i);
		}
	}
	return state;
}

char dfs()
{
	int i,j;
	bool flag = true;
	string now_state = make_hash();
	char sg_v = sg[now_state];
	
	if ( sg_v != 0) {//0 not visited, 1 is final number
		return sg_v; 
	}
	
	bool v[100];
	memset(v,false,sizeof(v));
	for (i=0;i<r-1;i++) {
		for (j=0;j<c-1;j++) {
			if (game[i][j]=='0' && game[i+1][j]=='0' && game[i][j+1]=='0' && game[i+1][j+1]=='0') {
				game[i][j] = game[i+1][j] = game[i][j+1] = game[i+1][j+1] = '1';
				v[ dfs()-'0' ] = true;
				game[i][j] = game[i+1][j] = game[i][j+1] = game[i+1][j+1] = '0';
				flag = false;
			}
		}
	}
	if (flag) {
		sg[now_state] = '0';
		return '0';
	}
	for (i=0;i<100;i++) {
		if (!v[i]) {
			sg[now_state] = i+'0';
			return i+'0';
		}
	}
}

int main()
{
	int i,j,k;
	int xor;
	sg.clear();
	while (scanf("%d",&n)==1) {
		xor = 0;
		for (i=0;i<n;i++) {
			scanf("%d %d",&r,&c);
			getchar();
			for (j=0;j<r;j++) {
				gets(game[j]);
			}
			xor ^= (dfs() -'0');
		}
		if (xor == 0) {
			puts("No");
		}
		else {
			puts("Yes");
		}
	}
}