自动搬运

查看原文

来自洛谷，原作者为

	TruchyR ¿啥你问了我我问了你啥?

搬运于2025-08-24 23:10:55，当前版本为作者最后更新于2025-02-06 14:05:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

出题人题解。

部分分

子任务 $0$ 考虑枚举每个位置是否放箱子再验证合法性。

子任务 $1$ 保证了不同位置很少，也可以搜索。

子任务 $2$ 留给可能过的网络流等算法。

子任务 $3$ 分两种情况，对向则最多放两个，否则考虑尽可能在每个拐角放。

子任务 $4$ 用于启发正解，做法和正解差不多。

正解

首先墙壁是诈骗，最优解肯定不用放墙。

假如我们在地图里放了多个箱子，那么这些箱子一定互不影响，即没有把一个箱子推进另一个箱子的情况。

由此我们可以假设地图上放满了箱子，用并查集维护移动过程。

• 左右转对这些箱子没有影响。
• 后退时退到的那一格内的那些箱子都不能放了。
• 前进时如果有把一些箱子推进另一些箱子的情况，直接把面前的箱子合并到更前面的箱子里。
  • 注意如果往墙上推就说明面前的那些箱子不能放。

最后在同一连通块的箱子只能放一个，注意箱子要动过的限制后随便选一个即可。

然后发现其实一个连通块只需要记录一个箱子的位置就可以了，于是在合并的时候优先记录被推动的箱子即可。

每组数据时间复杂度为 $O(nm+k)$。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define MX 2005
using namespace std;
const int CHECK=0,FIL=0;int read();
bitset<MX*MX> res,p;
int n,m,x,y,X,Y,f,a[MX*MX];string s;
int fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int Z(int i,int j){return i*m-m+j;}
int inMap(int i,int j){return i && j && i<=n && j<=m;}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	FRE freopen(".in","r",stdin);
	FRE freopen(".out","w",stdout);
	int T;cin>>T;while(T--){
		cin>>n>>m>>x>>y>>s>>s;X=x,Y=y,f=0;
		for(int i=1;i<=n*m;i++) a[i]=i,res[i]=p[i]=0;
		a[Z(x,y)]=0;
		for(auto i:s){
			if(i=='D') f=(f+1)%4;
			if(i=='A') f=(f+3)%4;
			if(i=='W'){
				int dx=x+fx[f][0],dy=y+fx[f][1];
				int wx=dx+fx[f][0],wy=dy+fx[f][1];
				if(a[Z(dx,dy)]){
					if(inMap(wx,wy)) a[Z(wx,wy)]=a[Z(dx,dy)];
					a[Z(dx,dy)]=0,p[Z(dx,dy)]=1;
				}
				x=dx,y=dy;
			}
			if(i=='S'){
				int dx=x-fx[f][0],dy=y-fx[f][1];
				a[Z(dx,dy)]=0;x=dx,y=dy;
			}
		}
		for(int i=1;i<=n*m;i++){
			if(!a[i]) continue;
			if(p[a[i]]) res[a[i]]=1;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i==X && j==Y){cout<<"X"; continue;}
				if(res[Z(i,j)]){cout<<"S";}
				else cout<<".";
			}cout<<'\n';
		}
	}
	return 0;
}
int read(){
	int Ca=0;char Cr=' ';int Cf=1;
	while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
	while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
	return Ca*Cf;
}