digital deletions(博弈搜索).cpp

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

#include <cstdio>
#include <string>

char cstr[10];
char hash[11][11][11][11][11][11];
struct inf {
	int len,A[10];
};

char dfs(inf a)
{
	char pre;
	int i,j;
	inf temp = a;
	if (a.len == 0) {//终态
		return 'L';
	}
	if (hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] != 0) {
		return hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]];
	}
	for (i=0;i<temp.len;i++) {
		a = temp;
		if (a.A[i] == 0) {
			for (j=i;j<6;j++) {
				a.A[j] = 10;
			}
			a.len = i;
			if (hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] == 0) {
				hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] = dfs(a);
			}
			if (hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] == 'L') {
				return 'W';
			}
		}
		else {
			for (j=temp.A[i]-1;j>=0;j--) {
				a.A[i] = j;
				if (hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] == 0) {
					hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] = dfs(a);
				}
				if (hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] == 'L') {
					return 'W';
				}
			}
		}
	}
	return 'L';
}

int main()
{
	inf a;
	memset(hash,0,sizeof(hash));//状态保持
	while (gets(cstr)) {
		a.len = strlen(cstr);
		for (int i=0;i<a.len;i++) {
			a.A[i] = cstr[i] - '0';
		}
		for (i=a.len;i<6;i++) {
			a.A[i] = 10;
		}
		if ( dfs(a) == 'W') {
			hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] = 'W';
			printf("Yes\n");
		}
		else {
			hash[a.A[0]][a.A[1]][a.A[2]][a.A[3]][a.A[4]][a.A[5]] = 'L';
			printf("No\n");
		}
	}
}