[POJ 2311] Cutting Game

[POJ 2311] Cutting Game

思路

可以用二维状态存SG函数值,$(2, 2)$,$(2, 3)$,$(3, 2)$为必败状态(即边界状态)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int sg[210][210], x, y;

int dfs(int x, int y){
	if(sg[x][y]!=-1)	return sg[x][y];
	bool vis[20010];
	memset(vis, 0, sizeof(vis));
	for(int i=2; 2*i<=x; i++)
		vis[dfs(x-i, y) ^ dfs(i, y)]=true;
	for(int i=2; 2*i<=y; i++)
		vis[dfs(x, y-i) ^ dfs(x, i)]=true;
	for(int i=0; i<=20000; i++)
		if(!vis[i])
			return sg[x][y]=i;
}

int main(){
	memset(sg, -1, sizeof(sg));
	sg[2][2]=sg[2][3]=sg[3][2]=0;
	while(scanf("%d%d", &x, &y)==2)
		printf(dfs(x, y)>0 ? "WIN\n" : "LOSE\n");
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注