能夠轉移到某個必敗狀態的為必勝狀態，只能轉移到必勝狀態的為必敗狀態。
根據這個遞推即可，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 閱讀(464)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：遞推/遞歸