问题描述:

给你一个$W*H$的矩形网格,两个人轮流水平或垂直地剪去一部分,如果轮到某个人只剩下1*1的网格时,则认为那个人输了。

输入:

有多组数据,每组数据两个数$W,H(2<=W,H<=200)$

输出:

每组数据一行,如果先手能赢输出”WIN”,否则”LOST”

思路:

代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 205
using namespace std;

int x[MAXN][MAXN], tag[MAXN<<3];

int sg(int n, int m)
{
    if(x[n][m]!=-1) return x[n][m];
    memset(tag, 0, sizeof(tag));
    for(int i=2; i<=n/2; i++) tag[sg(i, m)^sg(n-i, m)]=1;
    for(int i=2; i<=m/2; i++) tag[sg(n, i)^sg(n, m-i)]=1;
    for(int i=0; ;i++) if(tag[i]==0) {x[n][m]=i; return i;}
}

int main()
{
    int n, m;
    memset(x, -1, sizeof(x));
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        if(sg(n, m)) printf("WIN\n");
        else printf("LOSE\n");
    }
}

发表评论

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