解けはしたけどえらく苦労した。
http://codeforces.com/contest/1054/problem/E
問題
N*Mのグリッドがある。
各セルには01で構成された文字列が設定されている。
同様に、各セルには到達したい状態の文字列が設定されている。
下記の手順を、文字列の総数×4回まで用いて、到達先の状態にせよ。
- 同じ列または行に属する2つの異なるセルを選ぶ。そして片方の文字列の末尾の文字を、もう片方の文字列の先頭に追加する。
解法
まず01を別々に分け、再度割り振るということを行う。
0を左上、1を右下に集めるため、全てのマスにおいて、0を左端、1を右端に集めよう。
なお、すでに両端にある数字は、縦に移動させる。
そして各数字2回目の移動で0を左上、1を右下に集める。
次に、左1列目と、最下段を除くマスを目的の内容にする。
0は縦移動→横移動、1は横移動→縦移動の順で動かし、1文字ずつ追加していく。
次に、最下段・左1列目を同様に処理しよう。
残るは左上・右下・左下の4マスである。
これは、左上・右下・左下の順で格納すべき文字を順に左下に集め、再度左下から左上・右下に文字を移せばよい。
各文字最大4回しか移動しないので条件を満たす。
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]); }
まとめ
地味に手間取った。