久々に負の点数を取ってしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17625&rd=19264
問題
26*26の盤面で、最大26個のルークが置いてある。
これらはアルファベットが振られている。
ルークを合計で最大60回まで移動し、各ルークの配置がrow-major-orderで昇順に並ぶようにせよ。
解法
まず各行で横移動を行い、全ルークが異なる列に来るようにする。
その後、縦移動してn番目のアルファベットはn行目に来るようにすればよい。
どちらかというと難しいのは前者で、他のルークに移動経路を邪魔されないものを優先的に移動する必要がある。
int Y[26],X[26]; vector<int> ret; vector <string> S; class TwoDimensionalSort { public: void move(int r1,int c1,int r2,int c2) { if(r1==r2&&c1==c2) return; int dy=0; ret.push_back(r1); ret.push_back(c1); ret.push_back(r2); ret.push_back(c2); swap(S[r1][c1],S[r2][c2]); } vector <int> sortLetters(vector <string> board) { S=board; int N=26; MINUS(X); MINUS(Y); int y,x,i; ret.clear(); int TX[26]={}; MINUS(TX); int nex=0; FOR(y,N) { int cnt=0; deque<pair<int,int>> V; FOR(x,N) if(S[y][x]!='.') V.push_back({x,nex++}); while(V.size()) { FOR(i,V.size()) { if(V[i].first==V[i].second) { V.erase(V.begin()+i); break; } int L,R; if(V[i].first<V[i].second) { L=V[i].first+1; R=V[i].second; } else { L=V[i].second; R=V[i].first-1; } for(x=L;x<=R;x++) if(S[y][x]!='.') break; if(x==R+1) { move(y,V[i].first,y,V[i].second); V.erase(V.begin()+i); break; } } } } FOR(y,N) FOR(x,N) if(S[y][x]!='.') { move(y,x,S[y][x]-'A',x); } FOR(y,N) cout<<S[y]<<endl; return ret; } }
まとめ
うーん。