Codeforces #684 Div1 A2. Binary Table (Hard Version)

おおよそレート通りの出来だった回。
http://codeforces.com/contest/1439/problem/A2

問題

N*Mのグリッドが与えられる。
各セルは0か1が書かれている。
2*2の領域を選び、そのうち3つのセルの内容を0/1反転することを2*N*M回以下まで繰り返し、全セルの内容を0にせよ。

解法

左上から順に2*2領域をsweepしていき、上の行または左の列を0にするように3セルを選択していこう。
最終的に右下2*2領域に1が残るが、3手かければ2*2領域のうち1か所だけ0/1反転できるので、12手以内で全部0にできる。

int T;
int N,M;
int A[101][101];
string S;
vector<int> R;
void go(int r,int c) {
	R.push_back(r+1);
	R.push_back(c+1);
	A[r][c]^=1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(y,N) {
			cin>>S;
			FOR(x,M) A[y][x]=S[x]-'0';
		}
		R.clear();
		
		FOR(y,N-2) {
			FOR(x,M-1) {
				if(A[y][x]&&A[y][x+1]) {
					go(y,x);
					go(y,x+1);
					go(y+1,x+1);
				}
				else if(A[y][x]) {
					go(y,x);
					go(y+1,x);
					go(y+1,x+1);
				}
				else if(A[y][x+1]) {
					go(y,x+1);
					go(y+1,x);
					go(y+1,x+1);
				}
			}
		}
		y=N-2;
		FOR(x,M-2) {
			if(A[y][x]&&A[y+1][x]) {
				go(y,x);
				go(y+1,x);
				go(y,x+1);
			}
			else if(A[y][x]) {
				go(y,x);
				go(y,x+1);
				go(y+1,x+1);
			}
			else if(A[y+1][x]) {
				go(y+1,x);
				go(y,x+1);
				go(y+1,x+1);
			}
		}
		int num=A[N-2][M-2]+A[N-2][M-1]+A[N-1][M-2]+A[N-1][M-1];
		if(num==1) {
			int ty,tx;
			for(y=N-2;y<N;y++) for(x=M-2;x<M;x++) if(A[y][x]==1) ty=y,tx=x;
			for(y=N-2;y<N;y++) for(x=M-2;x<M;x++) {
				if(y==ty&&x==tx) continue;
				int sy,sx;
				for(sy=N-2;sy<N;sy++) for(sx=M-2;sx<M;sx++) if(sy!=y||sx!=x) go(sy,sx);
			}
		}
		else if(num==4) {
			for(y=N-2;y<N;y++) for(x=M-2;x<M;x++) {
				int sy,sx;
				for(sy=N-2;sy<N;sy++) for(sx=M-2;sx<M;sx++) if(sy!=y||sx!=x) go(sy,sx);
			}
		}
		else if(num==3) {
			for(y=N-2;y<N;y++) for(x=M-2;x<M;x++) if(A[y][x]==1) go(y,x);
		}
		else if(num==2) {
			vector<pair<int,int>> P[2];
			for(y=N-2;y<N;y++) for(x=M-2;x<M;x++) P[A[y][x]].push_back({y,x});
			go(P[0][0].first,P[0][0].second);
			go(P[0][1].first,P[0][1].second);
			go(P[1][0].first,P[1][0].second);
			go(P[0][0].first,P[0][0].second);
			go(P[0][1].first,P[0][1].second);
			go(P[1][1].first,P[1][1].second);
		}
		
		
		FOR(y,N) FOR(x,M) assert(A[y][x]==0);
		
		cout<<R.size()/6<<endl;
		FOR(i,R.size()/6) {
			FOR(j,6) cout<<R[i*6+j]<<" ";
			cout<<endl;
		}
		
	}
}

まとめ

もっと短く書けそうではあるが。