玩过俄罗斯方块?那你知道俄罗斯方块共有七种吧(其实只有五种)
给一个黑白图,每次能将某些区域的格子黑白反转,至于某些区域的意思嘛,就是俄罗斯方块形状的区域咯(可水平翻转、上下翻转、旋转)求能否将图变成全白Input
多组数据,第一行一个正整数 T,表示数据组数
每组数据中第一行两个正整数 n,m,表示图的长和宽
接下来 n 行,每行 m 个数字,表示第 i 行第 j 列的格子的颜色,0为白,1为黑T<=1000,∑n*m<=10000000
Output
对于每组数据,若能将图变成全白,则输出一行字符串"Yes",否则输出"No"(不包含双引号)
Input示例
1
4 4
0110
0110
1111
1111
Output示例
Yes
————————————————————————————————————————————————————————————————————————————————
这道题呢 我们可以靠一个 2x2 的矩阵将所有的 1 都转换到最后一行 和 最后一列
然后靠 1x4 将所有的一转换到最后一列 和 最下面一列 的三各
最后用 7 形状的 把问题转换成 右下角的三个格
最后发现偶数有解 奇数无解
在这个过程中我们又发现最后的奇偶 和 原来矩阵的 奇偶一样 这个就自己证明把
当然 1x? 和 2x2 需要特判一波
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int ans,T,n,m;
bool s[M];
char c;
bool isdigit(char c) {return c>='' && c<='';}
int main()
{
T=read();
while(T--){
n=read(); m=read();
if(n>m) swap(n,m);
while (!isdigit(c=getchar()));
if (n==){
for (int i=;i<m;i++) {s[i]=(c-''); while(!isdigit(c=getchar()));}
s[m]=(c-'');
for (int i=;i<=m-;i++)
if(s[i]) for(int j=;j<=;j++) s[i+j]^=;
if (s[m-]||s[m-]||s[m]) printf("No\n");
else printf("Yes\n");
}
else if (n==&&m==){
int ans=;
for (int i=;i<;i++){
ans+=(c-'');
while (!isdigit(c=getchar()));
}
ans+=(c-'');
if(ans==||!ans) printf("Yes\n");
else printf("No\n");
}
else{
int ans=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
if (i==n&&j==m) break;
ans+=(c-'');
while (!isdigit(c=getchar()));
}
ans+=(c-'');
if (ans%) printf("No\n");
else printf("Yes\n");
}
}
return ;
}