正题
题目大意
n
∗
n
n*n
n∗n的矩形，每一个人操作时如果棋盘上有一个
k
∗
k
k*k
k∗k的矩形空地就可以选择一个点堵上。如果没有就失败了，求必胜方。
解题思路
如果场地上有一个位置堵上后即可堵上所有
k
∗
k
k*k
k∗k的矩形那么这个点被堵住后就赢了，所以先手必胜。
如果没有这个位置，那么最后场地上剩下一个
k
∗
k
k*k
k∗k的矩形时先手必胜，也就是如果我们找出两个不相交的
k
∗
k
k*k
k∗k矩形那么显然先手不会去堵上这两个中的任何一个，也就是其他位置会被优先堵上。所以只要判断其他格子数量的奇偶性即可。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
const int N
=1100;
int n
,k
,a
[N
][N
],b
[N
][N
];
char s
[N
];
bool check(int x
,int y
)
{x
--;y
--;return (a
[x
+k
][y
+k
]+a
[x
][y
]-a
[x
][y
+k
]-a
[x
+k
][y
])==0;}
int main()
{
scanf("%d%d",&n
,&k
);
for(int i
=1;i
<=n
;i
++){
scanf("%s",s
+1);
for(int j
=1;j
<=n
;j
++)
a
[i
][j
]=a
[i
-1][j
]+a
[i
][j
-1]+(s
[j
]=='1')-a
[i
-1][j
-1];
}
int z
=0;
for(int i
=1;i
<=n
-k
+1;i
++)
for(int j
=1;j
<=n
-k
+1;j
++)
if(check(i
,j
)){
b
[i
][j
]++;b
[i
+k
][j
+k
]++;
b
[i
+k
][j
]--;b
[i
][j
+k
]--;
z
++;
}
bool flag
=1;
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++){
b
[i
][j
]+=b
[i
-1][j
]+b
[i
][j
-1]-b
[i
-1][j
-1];
if(b
[i
][j
]==z
)flag
=0;
}
if(flag
){
if((a
[n
][n
]-2*k
*k
)&1)printf("rx");
else printf("yc");
}
else{
if(z
)printf("rx");
else printf("yc");
}
}
