Mail.Ru Cup 2018 Round 1 : E. Chips Puzzle

解けはしたけどえらく苦労した。
http://codeforces.com/contest/1054/problem/E

問題

N*Mのグリッドがある。
各セルには01で構成された文字列が設定されている。
同様に、各セルには到達したい状態の文字列が設定されている。
下記の手順を、文字列の総数×4回まで用いて、到達先の状態にせよ。

• 同じ列または行に属する２つの異なるセルを選ぶ。そして片方の文字列の末尾の文字を、もう片方の文字列の先頭に追加する。

解法

まず01を別々に分け、再度割り振るということを行う。
0を左上、1を右下に集めるため、全てのマスにおいて、0を左端、1を右端に集めよう。
なお、すでに両端にある数字は、縦に移動させる。
そして各数字２回目の移動で0を左上、1を右下に集める。

次に、左１列目と、最下段を除くマスを目的の内容にする。
0は縦移動→横移動、1は横移動→縦移動の順で動かし、1文字ずつ追加していく。
次に、最下段・左１列目を同様に処理しよう。

残るは左上・右下・左下の４マスである。
これは、左上・右下・左下の順で格納すべき文字を順に左下に集め、再度左下から左上・右下に文字を移せばよい。

各文字最大４回しか移動しないので条件を満たす。

int H,W;
string S[1010][1010];
string T[1010][1010];
int C[2][1919];
vector<vector<int>> R;

void add(int y1,int x1,int y2,int x2) {
	if(y1==y2 && x1==x2) return;
	assert(y1!=y2 || x1!=x2);
	R.push_back({y1+1,x1+1,y2+1,x2+1});
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) {
		cin>>S[y][x];
		//FORR(c,S[y][x]) D[y][x].push_back(c);
	}
	
	FOR(y,H) FOR(x,W) {
		reverse(ALL(S[y][x]));
		FORR(c,S[y][x]) {
			if(c=='0') {
				if(x==0) {
					C[0][(y+1)%H]++;
					add(y,x,(y+1)%H,0);
				}
				else {
					C[0][y]++;
					add(y,x,y,0);
				}
			}
			else {
				if(x==W-1) {
					C[1][(y+1)%H]++;
					add(y,x,(y+1)%H,W-1);
				}
				else {
					C[1][y]++;
					add(y,x,y,W-1);
				}
			}
		}
	}
	
	FOR(y,H) {
		if(y) FOR(i,C[0][y]) add(y,0,0,0);
		if(y!=H-1) FOR(i,C[1][y]) add(y,W-1,H-1,W-1);
	}
	FOR(y,H) FOR(x,W) {
		cin>>T[y][x];
		reverse(ALL(T[y][x]));
		if(x>0 && y<H-1) {
			FORR(c,T[y][x]) {
				if(c=='0') {
					add(0,0,y,0);
					add(y,0,y,x);
				}
				else {
					add(H-1,W-1,H-1,x);
					add(H-1,x,y,x);
				}
			}
		}
	}
	
	for(y=1;y<H-1;y++) {
		x=0;
		FORR(c,T[y][x]) {
			if(c=='0') {
				add(0,0,y,0);
				add(y,0,y,x);
			}
			else {
				add(H-1,W-1,H-1,x);
				add(H-1,x,y,x);
			}
		}
	}
	for(x=1;x<W-1;x++) {
		y=H-1;
		FORR(c,T[y][x]) {
			if(c=='0') {
				add(0,0,y,0);
				add(y,0,y,x);
			}
			else {
				add(H-1,W-1,H-1,x);
				add(H-1,x,y,x);
			}
		}
	}
	
	FOR(i,3) {
		if(i==0) y=H-1,x=W-1;
		if(i==1) y=0,x=0;
		if(i==2) y=H-1,x=0;
		FORR(c,T[y][x]) {
			if(c=='0') add(0,0,H-1,0);
			else add(H-1,W-1,H-1,0);
		}
	}
	FOR(i,2) {
		if(i==0) y=H-1,x=W-1;
		if(i==1) y=0,x=0;
		FOR(j,T[y][x].size()) add(H-1,0,y,x);
	}
	
	_P("%d\n",R.size());
	FORR(r,R) _P("%d %d %d %d\n",r[0],r[1],r[2],r[3]);
}

まとめ

地味に手間取った。