P11113 [ROI 2024 Day 1] 2026 题解
思路
稍微拿样例手玩一下会发现：
- 形如
LL或LR的操作，前面的L不会对后面的盘面产生影响，可以删去。 - 形如
LUL的操作，后面的L不会对盘面产生影响，可以删去。
一通化简后，可以发现原操作变成了类似LURDLURDL这样不断循环的操作。
先模拟几次使所有块都到了角落后，可以维护每个块进行
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5,inf=1e9;
int T,n,m,siz,cntk;
int trans[22][N],b[N],pos[N];
char s[N],t[N];
string a[N],aa[N];
int mp[200];
inline void up(){
for(int j=0,now;j<m;j++){
now=0;
for(int i=0;i<n;i++){
if(a[i][j]!='.'){
a[now][j]=a[i][j];
if(now!=i)a[i][j]='.';
now++;
}
}
}
}
inline void down(){
for(int j=0,now;j<m;j++){
now=n-1;
for(int i=n-1;i>=0;i--){
if(a[i][j]!='.'){
a[now][j]=a[i][j];
if(now!=i)a[i][j]='.';
now--;
}
}
}
}
inline void left(){
for(int i=0,now;i<n;i++){
now=0;
for(int j=0;j<m;j++){
if(a[i][j]!='.'){
a[i][now]=a[i][j];
if(now!=j)a[i][j]='.';
now++;
}
}
}
}
inline void right(){
for(int i=0,now;i<n;i++){
now=m-1;
for(int j=m-1;j>=0;j--){
if(a[i][j]!='.'){
a[i][now]=a[i][j];
if(now!=j)a[i][j]='.';
now--;
}
}
}
}
inline void Up(){
for(int j=0,now;j<m;j++){
now=0;
for(int i=0;i<n;i++){
if(b[i*m+j]!=0){
b[now*m+j]=b[i*m+j];
if(now!=i)b[i*m+j]=0;
now++;
}
}
}
}
inline void Down(){
for(int j=0,now;j<m;j++){
now=n-1;
for(int i=n-1;i>=0;i--){
if(b[i*m+j]!=0){
b[now*m+j]=b[i*m+j];
if(now!=i)b[i*m+j]=0;
now--;
}
}
}
}
inline void Left(){
for(int i=0,now;i<n;i++){
now=0;
for(int j=0;j<m;j++){
if(b[i*m+j]!=0){
b[i*m+now]=b[i*m+j];
if(now!=j)b[i*m+j]=0;
now++;
}
}
}
}
inline void Right(){
for(int i=0,now;i<n;i++){
now=m-1;
for(int j=m-1;j>=0;j--){
if(b[i*m+j]!=0){
b[i*m+now]=b[i*m+j];
if(now!=j)b[i*m+j]=0;
now--;
}
}
}
}
inline bool work(){
if(siz<=2)return 0;
for(int i=1;i<=siz+5;i++)t[i]=0;
t[1]=s[1],t[2]=s[2];
for(int i=2,j=1;;){
if(mp[t[j]]/2==mp[t[j+1]]/2){
t[j]=t[j+1],t[j+1]=0;
if(j!=1)j--;
else{
if(i==siz)break;
else t[j+1]=s[++i];
}
}else if(t[j-1]==t[j+1]){
t[j+1]=0;
if(j!=1)j--;
else{
if(i==siz)break;
else t[j+1]=s[++i];
}
}else{
if(i==siz)break;
else{
i++,j++;
t[j+1]=s[i];
}
}
}
int l=strlen(t+1);
if(t[l]==t[l-1])l--;
for(int i=1;i<=l;i++){
s[i]=t[i];
// cout<<s[i];
}
// cout<<"\n"<<l<<"\n";
if(siz==l)return 0;
siz=l;
return 1;
}
inline void move(int i){
// cntk++;
if(s[i]=='U')up();
else if(s[i]=='D')down();
else if(s[i]=='L')left();
else if(s[i]=='R')right();
}
inline void bin(){
for(int i=1;i<=3;i++)move(i);
int cnt=0;
for(int i=0;i<n;i++){
aa[i]=a[i];
for(int j=0;j<m;j++){
if(a[i][j]=='.')b[i*m+j]=0;
else{
b[i*m+j]=++cnt;
pos[cnt]=i*m+j;
}
}
}
for(int i=4;i<=7;i++){//这里是大写，千万别改move
if(s[i]=='U')Up();
else if(s[i]=='D')Down();
else if(s[i]=='L')Left();
else if(s[i]=='R')Right();
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(b[i*m+j]==0)continue;
trans[0][pos[b[i*m+j]]]=i*m+j;//pos->pos;
}
}
int tim=(siz-3)/4;
// return ;
for(int k=1;(1<<k)<=tim;k++){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(b[i*m+j]==0)continue;
trans[k][i*m+j]=trans[k-1][trans[k-1][i*m+j]];
}
}
}
for(int k=0;(1<<k)<=tim;k++){
int bi=(1<<k);
if((tim&bi)==0)continue;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]=='.'){
aa[i][j]='.';continue;
}
int x=trans[k][i*m+j]/m,y=trans[k][i*m+j]%m;
aa[x][y]=a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
swap(a[i][j],aa[i][j]);
}
}
}
for(int i=3+tim*4;i<=siz;i++)move(i);
}
char _[N];
inline void solve(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",_+1);
a[i].resize(m);
for(int j=0;j<m;j++)a[i][j]=_[j+1];
}
scanf("%s",s+1);
siz=strlen(s+1);
work();
if(siz<=5){
for(int i=1;i<=siz;i++){
move(i);
}
}else bin();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)putchar(a[i][j]);
printf("\n");
}
}
int main(){
// freopen("02.in","r",stdin);
// freopen("out.txt","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
mp['L']=0,mp['R']=1,mp['U']=2,mp['D']=3;
// solve();
// return 0;
scanf("%d",&T);
while(T--){
solve();
}
// cout<<cntk;
return 0;
}/*
*/