自动搬运

查看原文

来自洛谷，原作者为

	WhitD %$@oma

搬运于2025-08-24 22:50:14，当前版本为作者最后更新于2023-09-10 20:36:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

你有一个机器人，初始坐标位于 $(0,0)$，有一个地雷位于 $(x,y)$，给你一串操作符（由 U,D,L,R 构成）。

U 能让机器人从 $(x,y)$ 移动到 $(x,y+1)$，D 能让机器人从 $(x,y)$ 移动到 $(x,y-1)$，L 能让机器人从 $(x,y)$ 移动到 $(x-1,y)$，R 能让机器人从 $(x,y)$ 移动到 $(x+1,y)$。

你可以将操作符重新排序（只能改变顺序，不能改变个数），问是否存在一种方案使机器人不会踩到地雷，如果存在则输出此方案，否则输出 Impossible。

思路

我们发现同一种操作符的先后顺序变化是没有影响的，那我们可以把同种字符串都放到一起执行，例如样例中的 RURULLD 实际上等价于 RRUULLD。

而不同种操作符的先后顺序变化是有影响的，所以我们可以暴力枚举每种操作符在操作序列中的先后顺序，事实上共有 $4!=24$ 种排列方案（其实就是全排列），然后判断每种方案是否合法。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int T;
int main()
{
	cin>>T;
	while(T--)
	{
		int x,y,u=0,d=0,l=0,r=0,p[5],op=0;
		string s;
		cin>>x>>y>>s;swap(x,y);
		int len=s.size();
		for(int i=0;i<len;i++)
		{
			if(s[i]=='U')
				u++;
			if(s[i]=='D')
				d++;
			if(s[i]=='L')
				l++;
			if(s[i]=='R')
				r++;
		}
		for(int i=1;i<=4;i++)
			p[i]=i;
		do
		{
			int dx=0,dy=0,flag=1;
			for(int i=1;i<=4;i++)
			{
				if(p[i]==3&&dx==x&&y>=dy-l&&y<=dy)
				{
					flag=0;
					break;
				}
				else if(p[i]==4&&dx==x&&y<=dy+r&&y>=dy) 
				{
					flag=0;
					break;
				} 
				else if(p[i]==1&&dy==y&&x>=dx&&x<=dx+u)
				{
					flag=0;
					break;
				} 
				else if(p[i]==2&&dy==y&&x>=dx-d&&x<=dx)
				{
					flag=0;
					break;
				}
					if(p[i]==1)
						dx+=u;
					if(p[i]==2)
						dx-=d;
					if(p[i]==3)
						dy-=l; 
					if(p[i]==4)
						dy+=r;
			}
			if(flag)
			{
				for(int i=1;i<=4;i++)
				{
					if(p[i]==1)
						for(int j=1;j<=u;j++)
							cout<<"U";
					if(p[i]==2)
						for(int j=1;j<=d;j++)
							cout<<"D";
					if(p[i]==3)
						for(int j=1;j<=l;j++)
							cout<<"L";
					if(p[i]==4)
						for(int j=1;j<=r;j++)
							cout<<"R";
				}
				cout<<endl;
				op=1;
				break;
			}
		}while(next_permutation(p+1,p+5));
		if(!op)
			cout<<"Impossible"<<endl;
	}
	return 0;
}