codeforces1439A2. Binary Table (Hard Version)

https://codeforces.com/contest/1439/problem/A2

上來兩構造題，直接痛苦面具，還好過的不是很慢，，，

從上往下搞，從左向右搞，只要當前為1，不管右邊和下面是什么，直接把他變成0

然后考慮最下面兩行，從左到右列舉列，不管右邊是什么，當前是1，就選當前和右邊兩個

然后對于右下角的2*2格子，有4個，就先選3個，再搞剩下一個，由A1知道，對于任意一個1，我們可以用3次操作，實作不改變其他格子，把他變0了，

有3個，就直接選了，有2個，就選2個再選1個0，再把多出來的這個1搞了

1個就直接搞

這樣對于前面部分，每個格子只會被列舉到一次，對于右下角2*2的方塊，我們可以用4次以內的操作全變0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxl=110;

int n,m,cnt,cas,tot,ans;
int a[maxl][maxl];
bool vis[maxl];
char s[maxl];
struct node
{
	int x,y;
};
vector<node> b;

inline void prework()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			a[i][j]=s[j]-'0';
	}
}

inline void gao(int i,int j)
{
	if(i+1<=n && j+1<=m)
			{
				b.push_back(node{i,j});
				b.push_back(node{i+1,j});
				b.push_back(node{i,j+1});
				b.push_back(node{i,j});
				b.push_back(node{i+1,j});
				b.push_back(node{i+1,j+1});
				b.push_back(node{i,j});
				b.push_back(node{i,j+1});
				b.push_back(node{i+1,j+1});
			}
			else if(i==n)
			{
				if(j==m)
				{
					b.push_back(node{i,j});
					b.push_back(node{i-1,j});
					b.push_back(node{i,j-1});
					b.push_back(node{i,j});
					b.push_back(node{i-1,j});
					b.push_back(node{i-1,j-1});
					b.push_back(node{i,j});
					b.push_back(node{i,j-1});
					b.push_back(node{i-1,j-1});
				}
				else
				{
					b.push_back(node{i,j});
					b.push_back(node{i,j+1});
					b.push_back(node{i-1,j});
					b.push_back(node{i,j});
					b.push_back(node{i,j+1});
					b.push_back(node{i-1,j+1});
					b.push_back(node{i,j});
					b.push_back(node{i-1,j});
					b.push_back(node{i-1,j+1});
				}
			}
			else
			{
				b.push_back(node{i,j});
				b.push_back(node{i,j-1});
				b.push_back(node{i+1,j});
				b.push_back(node{i,j});
				b.push_back(node{i,j-1});
				b.push_back(node{i+1,j-1});
				b.push_back(node{i,j});
				b.push_back(node{i+1,j});
				b.push_back(node{i+1,j-1});
			}
}

inline void mainwork()
{
	b.clear();
	for(int i=1;i<=n-2;i++)
		for(int j=1;j<=m;j++)
		if(a[i][j])
		{
			if(j<m)
			{
				b.push_back(node{i,j});a[i][j]^=1;
				b.push_back(node{i,j+1});a[i][j+1]^=1;
				b.push_back(node{i+1,j});a[i+1][j]^=1;
			}
			else
			{
				b.push_back(node{i,j});a[i][j]^=1;
				b.push_back(node{i+1,j});a[i+1][j]^=1;
				b.push_back(node{i+1,j-1});a[i+1][j-1]^=1;
			}
		}
	for(int j=1;j<=m-2;j++)
	{
		if(a[n-1][j])
		{
			int i=n-1;
			b.push_back(node{i,j});a[i][j]^=1;
			b.push_back(node{i,j+1});a[i][j+1]^=1;
			b.push_back(node{i+1,j+1});a[i+1][j+1]^=1;
		}
		if(a[n][j])
		{
			int i=n;
			b.push_back(node{i,j});a[i][j]^=1;
			b.push_back(node{i,j+1});a[i][j+1]^=1;
			b.push_back(node{i-1,j+1});a[i-1][j+1]^=1;
		}
	}
	cnt=0;
	for(int i=n-1;i<=n;i++)
		for(int j=m-1;j<=m;j++)
		if(a[i][j])
			++cnt;
	if(cnt>=3)
	{
		int now=0;
		for(int i=n-1;i<=n;i++)
			for(int j=m-1;j<=m;j++)
			if(a[i][j])
			{	
				b.push_back(node{i,j});a[i][j]=0;
				++now;if(now==3) break;
			}
		for(int i=n-1;i<=n;i++)
			for(int j=m-1;j<=m;j++)
			if(a[i][j])
				gao(i,j),a[i][j]=0;
	}
	else if(cnt==2)
	{
		for(int i=n-1;i<=n;i++)
			for(int j=m-1;j<=m;j++)
			if(a[i][j])
				b.push_back(node{i,j});
		int x,y;
		for(int i=n-1;i<=n;i++)
			for(int j=m-1;j<=m;j++)
			if(!a[i][j])
			{	
				b.push_back(node{i,j});
				gao(i,j);
				a[n-1][m-1]=a[n-1][m]=a[n][m-1]=a[n][m]=0;
				return;
			}
	}
	else if(cnt==1)
	{
		for(int i=n-1;i<=n;i++)
			for(int j=m-1;j<=m;j++)
			if(a[i][j])
				gao(i,j),a[i][j]=0;
	}
}

inline void print()
{
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		if(a[i][j])
			puts("wa");
	int k=b.size();
	printf("%d\n",k/3);
	for(int i=0;i<k/3;i++)
		printf("%d %d %d %d %d %d\n",b[i*3].x,b[i*3].y,b[i*3+1].x,b[i*3+1].y,b[i*3+2].x,b[i*3+2].y);
}

int main()
{
	int t=1;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		prework();
		mainwork();
		print();
	}	
	return 0;
}