第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）签到题E Evil Coordinate

problem

链接：https://ac.nowcoder.com/acm/contest/10272/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
A robot is standing on an infinite 2-dimensional plane. Programmed with a string s_1s_2\cdots s_ns
1
​
s
2
​
⋯s
n
​
of length nn, where s_i \in {\text{‘U’}, \text{‘D’}, \text{‘L’}, \text{‘R’}}s
i
​
∈{’U’,’D’,’L’,’R’}, the robot will start moving from (0, 0)(0,0) and will follow the instructions represented by the characters in the string.

More formally, let (x, y)(x,y) be the current coordinate of the robot. Starting from (0, 0)(0,0), the robot repeats the following procedure nn times. During the ii-th time:
If s_i = \text{‘U’}s
i
​
=’U’ the robot moves from (x, y)(x,y) to (x, y+1)(x,y+1);
If s_i = \text{‘D’}s
i
​
=’D’ the robot moves from (x, y)(x,y) to (x, y-1)(x,y−1);
If s_i = \text{‘L’}s
i
​
=’L’ the robot moves from (x, y)(x,y) to (x-1, y)(x−1,y);
If s_i = \text{‘R’}s
i
​
=’R’ the robot moves from (x, y)(x,y) to (x+1, y)(x+1,y).

However, there is a mine buried under the coordinate (m_x, m_y)(m
x
​
,m
y
​
). If the robot steps onto (m_x, m_y)(m
x
​
,m
y
​
) during its movement, it will be blown up into pieces. Poor robot!

Your task is to rearrange the characters in the string in any order, so that the robot will not step onto (m_x, m_y)(m
x
​
,m
y
​
).
输入描述:
There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:

The first line contains two integers m_xm
x
​
and m_ym
y
​
(-10^9 \le m_x, m_y \le 10^9−10
9
≤m
x
​
,m
y
​
≤10
9
) indicating the coordinate of the mine.

The second line contains a string s_1s_2\cdots s_ns
1
​
s
2
​
⋯s
n
​
of length nn (1 \le n \le 10^51≤n≤10
5
, s_i \in {\text{‘U’}, \text{‘D’}, \text{‘L’}, \text{‘R’}}s
i
​
∈{’U’,’D’,’L’,’R’}) indicating the string programmed into the robot.

It’s guaranteed that the sum of nn of all test cases will not exceed 10^610
6
.
输出描述:
For each test case output one line. If a valid answer exists print the rearranged string, otherwise print “Impossible” (without quotes) instead. If there are multiple valid answers you can print any of them.
示例1
输入
复制
5
1 1
RURULLD
0 5
UUU
0 3
UUU
0 2
UUU
0 0
UUU
输出
复制
LDLRUUR
UUU
Impossible
Impossible
Impossible

solution

题意：

• 给出一个字符串，UDLR分别表示向上下左右移动。默认在坐标原点(0,0)，求更改字符顺序，让其移动不经过题目地雷点(mx,my)。

思路：

• 可以证明存在一种答案，使得相同的方向是连续排在一起的，即枚举UDLR的24种排列即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const char a[]="UDLR";//用0123对应ULDR，a是字符，c是数量，q是排列。
const int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
int main(){
	//ios::sync_with_stdio(false); WA
	int T;  cin>>T;
	while(T--){
		int mx, my;  cin>>mx>>my;
		string s;  cin>>s;
		int c[4] = {};
		for(int i=0;i<s.size();i++){
			if(s[i]=='U')c[0]++;
			if(s[i]=='D')c[1]++;
			if(s[i]=='L')c[2]++;
			if(s[i]=='R')c[3]++;
		}
		//for(int i =0; i<4;i++)cout<<c[i]<<"\n";
		
		//起点或终点重合
		int tx=c[3]-c[2],ty=c[0]-c[1];
		if(tx==mx&&ty==my || mx==0&&my==0){
			cout<<"Impossible\n";
			continue;
		}
		
		int q[4]={0,1,2,3}, ook=0;
		do{
			int x=0,y=0,ok=1;
			for(int i=0; i<=3; i++){//方向
				for(int j=0;j<c[q[i]];j++){//移动(方向q[i]有长度c[q[i]])
					x += dx[q[i]], y+=dy[q[i]];
					if(x==mx&&y==my){
						ok=0; break;
					}
				}
				if(ok==0)break;
			}
			if(ok==1){//没有雷就全方向输出
				for(int i=0; i<=3; i++)
					for(int j=0; j<c[q[i]];j++)
						putchar(a[q[i]]);
				cout<<"\n";
				ook=1;
				break;
			}
		}while(next_permutation(q,q+4));
		if(ook)continue;
		cout<<"Impossible\n";
	}
	return 0;
}

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/111503806