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;