Madoka and Childish Pranks + greedy

这道题也是一个对图进行operation的题目，需要用到贪心的思想：

分析题干：这里其实题目并没有说清楚，这里的chess coloring其实指的不只是是左上角那个方块涂成白色，其他就可以随便涂；其实是对于选出来的那个子矩阵，我们将其行号和列号加起来，和为偶数的涂成白色，和为奇数的涂成黑色；

  但是我们如果真的如题目中test1那样去的话，我们根本不能掌控这样操作后会有什么结果，所以我要让我操作的格子尽可能地少；

  于是，我们每次取子矩阵就只需取1X2或者2X1的子矩阵即可，然后根据是否在第一行采用不同的子矩阵，我们可以发现因为这个矩阵原来就是白的，所以我只对当前需要的(i,j)进行染色，也就是说这样的话我每次都是精准的进行涂色，有多少个1，我就取多少个子矩阵。

代码：

#include

using namespace std;

int main()
{
int t;
cin >> t;
while(t--){
int ans[50010];
char q[105][105];
int n,m;
cin >> n >> m;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++){
cin >> q[i][j];
}

if(q[1][1] == '1') cout << -1 << '\n';
else {
int k = 1;
int cnt = 0;
for(int i = n;i>=1;i--){
for(int j = m;j>=1;j--){
if(q[i][j] == '1' && i>1){
cnt++;
ans[k++] = i-1;
ans[k++] = j;
ans[k++] = i;
ans[k++] = j;
}
else if(q[i][j] == '1' && i==1){
cnt++;
ans[k++] = i;
ans[k++] = j-1;
ans[k++] = i;
ans[k++] = j;
}
}
}

cout << cnt << '\n';
for(int i = 1;i
cout << ans[i] <<" "<< ans[++i] <<" " <
}
}
}
return 0;
}

 分析：这里值得注意的是因为我每对一个格子染色就要入四个点，所以我开的数组要超过1e4；