GMOJ 6826. 【2020.10.17提高组模拟】隔膜（lcyrcx）

 这道题是一道结论题。

考虑分类讨论。

1. 当棋盘上只有一个合法的正方形或者多个相交于一点的正方形时，显然先手必胜。
2. 当棋盘上有两个及以上的不相交正方形时，容易发现，不管棋盘状态如何，最终都会转移成有两个不相交的正方形，其他点全部都已经被走过的方案。那么此时一定是后手必胜。所以可以判断棋盘上其他空点的奇偶性来做这道题。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2000
using namespace std;
int n,k,i,j,l,r,map[N][N],ans,tp,bz[N][N],sum,sum1,bzk;
char ch[N];
int main(){
    freopen("lcyrcx.in","r",stdin);
    freopen("lcyrcx.out","w",stdout);
    scanf("%d%d
",&n,&k);
    for (i=1;i<=n;i++){
        scanf("%s",ch+1);
        for (j=1;j<=n;j++){
            map[i][j]=ch[j]-'0';
            if (!map[i][j]) sum++;
        }
    }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (bz[i][j]+map[l][j]==0&&n-i+1>=k&&n-j+1>=k){
                bzk=0;
                for (r=j;r<=j+k-1;r++){
                    for (l=i;l<=i+k-1;l++){
                        if (map[l][r]+bz[l][r]>=1){
                            bzk=1;
                            break;
                        }
                        bz[l][r]=1;
                    }
                    if (bzk) break;
                }
                if (bzk==0) sum1++;
            }
    if (sum1==1||(sum-k*k*2)%2==1&&sum1>=2)
        printf("rx
");
    else
        printf("yc
");
    return 0;
}