自动搬运

查看原文

来自洛谷，原作者为

	LDR___ 统计数据非实时更新。

搬运于2025-08-24 23:04:20，当前版本为作者最后更新于2024-10-25 11:53:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

稍微拿样例手玩一下会发现：

• 形如LL或LR的操作，前面的L不会对后面的盘面产生影响，可以删去。
• 形如LUL的操作，后面的L不会对盘面产生影响，可以删去。

一通化简后，可以发现原操作变成了类似LURDLURDL这样不断循环的操作。

先模拟几次使所有块都到了角落后，可以维护每个块进行 $2^i$ 次循环操作后所在的位置，倍增加速后续操作即可。

代码

#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;
}/*
*/