問題概要
のグリッドが与えられ、このグリッドを上下左右方向に傾けてタイルを動かす操作を行う。操作列は、(操作)*数字のように圧縮された状態で与えられる。最終的なタイルの状態を求めよ。
制約
解法
タイルに書かれた文字を無視すると、一度四隅のいずれかに寄った状態になればその後取りうる状態は4通りに限られる。
また、この問題で考察したように左回りor右回りに何回転したかが分かれば周期を用いて最終状態を求めることができる。
各操作列は、初期状態(4隅のうちどこに寄っているか)に対してその操作を行うと、(どの隅に移動するか,その際左右に何回転するか)を対応付ける写像として見ることが出来ます。
上で述べた対応付けを4つの初期状態ぞれぞれについて求めればよくて、これを構文解析をしながら実装します。掛け算パートはダブリングをしました。実装は頑張りましょう。
L/Rしか存在しない操作列・U/Dしか存在しない操作列、の場合は簡単に解くことができて、これを予め除いておくと全て最終形が四隅に寄る話に帰着させることができます。
4隅のいずれかに寄る場合の初期状態は、操作列の括弧と数字を取り除いた文字列において初めて横方向の移動と縦方向の移動が隣接する部分を抜き出せば良いです。
実装
309行あって草 もっと綺麗に書けるはず……
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef unsigned long long ull; // 方向 0:D 1:R 2:U 3:L // 状態 0:LU 1:LD 2:RD 3:RU // 右回りを正とする int Get[4][4]={ {1,3,0,0}, {1,2,0,1}, {2,2,3,1}, {2,3,3,0} }; int cnt_rotate[4][4]={ {0,-1,0,0}, {0,0,0,0}, {0,0,0,0}, {0,0,0,1} }; map<char,int> mp; // 方向→数字 void init(vector<vector<int>> &v){ int n=v[0].size(); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ v[i][j]=0; } } } vector<vector<int>> Down(vector<vector<int>> a){ vector<vector<int>> b=a; init(b); int n=a[0].size(); for(int i=0;i<n;i++){ int cur=n-1; for(int j=n-1;j>=0;j--){ if(a[j][i]){ b[cur][i]=a[j][i]; cur--; } } } return b; } vector<vector<int>> Right(vector<vector<int>> a){ vector<vector<int>> b=a; init(b); int n=a[0].size(); for(int i=0;i<n;i++){ int cur=n-1; for(int j=n-1;j>=0;j--){ if(a[i][j]){ b[i][cur]=a[i][j]; cur--; } } } return b; } vector<vector<int>> Up(vector<vector<int>> a){ vector<vector<int>> b=a; init(b); int n=a[0].size(); for(int i=0;i<n;i++){ int cur=0; for(int j=0;j<n;j++){ if(a[j][i]){ b[cur][i]=a[j][i]; cur++; } } } return b; } vector<vector<int>> Left(vector<vector<int>> a){ vector<vector<int>> b=a; init(b); int n=a[0].size(); for(int i=0;i<n;i++){ int cur=0; for(int j=0;j<n;j++){ if(a[i][j]){ b[i][cur]=a[i][j]; cur++; } } } return b; } void print_res(vector<vector<int>> s,vector<char> v){ int n=s[0].size(); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ printf("%c",v[s[i][j]]); } printf("\n"); } } void solve2(vector<vector<int>> s,string t,vector<char> v){ reverse(t.begin(), t.end()); char dir; for(char c:t){ if(c=='R' or c=='L' or c=='D' or c=='U'){ dir=c; break; } } if(dir=='R')s=Right(s); if(dir=='L')s=Left(s); if(dir=='U')s=Up(s); if(dir=='D')s=Down(s); print_res(s,v); } int id=0; vector<pair<int,ll>> solve(string t){ vector<pair<int,ll>> res(4); for(int i=0;i<4;i++){ res[i]=make_pair(i,0LL); } for(;id<t.size();id++){ if(t[id]=='('){ id++; auto R=solve(t); id++; ll num=0; while(id<t.size() and '0'<=t[id] and t[id]<='9'){ num=num*10+t[id]-'0'; id++; } id--; // ここで掛け算処理を書く vector<vector<pair<int,ll>>> mul(61,vector<pair<int,ll>>(4)); for(int i=0;i<4;i++){ mul[0][i]=R[i]; } for(int i=1;i<61;i++){ for(int j=0;j<4;j++){ mul[i][j].first=mul[i-1][mul[i-1][j].first].first; mul[i][j].second=mul[i-1][j].second+mul[i-1][mul[i-1][j].first].second; } } for(int i=60;i>=0;i--){ if((1LL<<i)&num){ for(int j=0;j<4;j++){ int cur=res[j].first; res[j].first=mul[i][cur].first; res[j].second+=mul[i][cur].second; } } } } else if(t[id]==')'){ return res; } else{ int op=mp[t[id]]; for(int i=0;i<4;i++){ int cur=res[i].first; res[i].first=Get[cur][op]; res[i].second+=cnt_rotate[cur][op]; } } } return res; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; mp['D']=0,mp['R']=1,mp['U']=2,mp['L']=3; while(cin >> n,n){ vector<string> S(n); vector<vector<int>> s(n,vector<int>(n)); for(int i=0;i<n;i++){ cin >> S[i]; } string t; cin >> t; vector<char> V={'.'}; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(S[i][j]!='.'){ s[i][j]=(int)V.size(); V.push_back(S[i][j]); } else s[i][j]=0; } } if(V.size()==1){ print_res(s,V); continue; } bool flag1=true; // UD only bool flag2=true; // RL only for(char c:t){ if(c=='R' or c=='L')flag1=false; if(c=='U' or c=='D')flag2=false; } if(flag1^flag2){ solve2(s,t,V); continue; } vector<char> dir; for(char c:t){ if(c=='R' or c=='L' or c=='U' or c=='D')dir.push_back(c); } int cur; for(int i=0;i+1<dir.size();i++){ if(dir[i]=='R' or dir[i]=='L'){ if(dir[i+1]=='U' or dir[i+1]=='D'){ if(dir[i]=='L'){ s=Left(s); if(dir[i+1]=='U'){cur=0;s=Up(s);} else{cur=1;s=Down(s);} } else{ s=Right(s); if(dir[i+1]=='D'){cur=2;s=Down(s);} else{cur=3;s=Up(s);} } break; } } else{ if(dir[i+1]=='R' or dir[i+1]=='L'){ if(dir[i+1]=='L'){ if(dir[i]=='U'){cur=0;s=Up(s);} else{cur=1;s=Down(s);} s=Left(s); } else{ if(dir[i]=='D'){cur=2;s=Down(s);} else{cur=3;s=Up(s);} s=Right(s); } } } } id=0; auto Op=solve(t); auto op=Op[cur]; if(cur==3){ s=Down(s); s=Left(s); s=Up(s); } else if(cur==2){ s=Left(s); s=Up(s); } else if(cur==1){ s=Up(s); } auto ss=s; ss=Down(ss); ss=Right(ss); ss=Up(ss); ss=Left(ss); set<int> used; map<int,pair<int,int>> pos1,pos2; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ pos1[s[i][j]]=make_pair(i,j); pos2[ss[i][j]]=make_pair(i,j); } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(s[i][j]==0)continue; if(used.find(s[i][j])!=used.end())continue; int now=s[i][j]; vector<int> num; vector<pair<int,int>> num_pos; pair<int,int> cur_pos=make_pair(i,j); while(used.find(now)==used.end()){ used.insert(now); num.push_back(now); num_pos.push_back(cur_pos); pair<int,int> nx_pos=pos2[now]; int nx=s[nx_pos.first][nx_pos.second]; now=nx; cur_pos=nx_pos; } int len=num.size(); ll cycle=op.second; cycle%=len; if(cycle<0)cycle+=len; for(int k=0;k<len;k++){ int kid=(k+cycle)%len; s[num_pos[kid].first][num_pos[kid].second]=num[k]; } } } if(op.first==1){ s=Down(s); } else if(op.first==2){ s=Down(s); s=Right(s); } else if(op.first==3){ s=Down(s); s=Right(s); s=Up(s); } print_res(s,V); } }
