poj 2311 Cutting Game nim與狀態的grundy值

題意：

給一個w*h的矩形，兩人輪流只能沿格子的邊緣橫剪或豎剪，最先剪出1*1的格子的人獲勝，問先手必勝還是必敗。

分析：

此題要求對grundy值有理解。一個全局狀態的grundy值是對游戲中某個狀態的有效的描述，grundy值描述了當前狀態的所有後繼狀態，比如n堆石子的nim游戲的grundy值是a1^a2^...an。

代碼：

//poj 2311
//sep9
#include 
#include 
using namespace std;
const int maxN=256;
int dp[256][256];

int grundy(int w,int h)
{
	if(dp[w][h]!=-1) return dp[w][h];	
	set s;
	for(int i=2;w-i>=2;++i) s.insert(grundy(i,h)^grundy(w-i,h));
	for(int i=2;h-i>=2;++i) s.insert(grundy(w,i)^grundy(w,h-i));
	int res=0;
	while(s.count(res)) res++;
	return dp[w][h]=res;
}

int main()
{
	memset(dp,-1,sizeof(dp));
	int w,h;
	while(scanf("%d%d",&w,&h)==2){
		if(grundy(w,h)!=0) puts("WIN");
		else puts("LOSE"); 		
	}	
	return 0;	
}