能够转移到某个必败状态的为必胜状态，只能转移到必胜状态的为必败状态。
根据这个递推即可，d[i][j]==1表示在i*j的棋盘上游戏，kiki必胜。
网上许多人对于这道题是判断奇偶性：先递推，然后发现规律。
开2000×2000的bool数组会超空间，使用bitset即可。
以下是我的代码：
#include<bitset>
#include<cstdio>
using namespace std;
const int dx[]={0,-1,-1},dy[]={-1,0,-1};
bitset<2007> d[2007];
void Init()
{
d[1][1]=1;
for(int i=1;i<=2000;i++)
for(int j=1;j<=2000;j++)
{
bool success(false);
for(int k=0;k<3;k++)
{
int ii(i+dx[k]),jj(j+dy[k]);
if(ii<=0 || jj<=0)
continue;
if(d[ii][jj]==0)
{
d[i][j]=1;
success=true;
break;
}
}
if(!success)
d[i][j]=0;
}
}
int main()
{
Init();
int n,m;
while(scanf("%d%d",&n,&m)==2 && (n || m))
if(d[n][m])
printf("Wonderful!\n");
else
printf("What a pity!\n");
return 0;
}
posted on 2011-05-08 11:41
lee1r 阅读(427)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：递推/递归