题目
链接：https://ac.nowcoder.com/acm/contest/10272/E
来源：牛客网
题目描述
A robot is standing on an infinite 2-dimensional plane. Programmed with a string (s_1s_2cdots s_n)
of length n, where (s_i in { ext{'U'}, ext{'D'}, ext{'L'}, ext{'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 = ext{'U'}) the robot moves from (x, y)(x,y) to (x, y+1)(x,y+1);
If (s_i = ext{'D'})the robot moves from (x, y)(x,y) to (x, y-1)(x,y−1);
If (s_i = ext{'L'}) the robot moves from (x, y)(x,y) to (x-1, y)(x−1,y);
If (s_i = ext{'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)). If the robot steps onto ((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))
输入描述:
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_x) and (m_y)
((-10^9 le m_x, m_y le 10^9))indicating the coordinate of the mine.
The second line contains a string (s_1s_2cdots s_n)of length n ((1 le n le 10^5))
, (s_i in { ext{'U'}, ext{'D'}, ext{'L'}, ext{'R'}}) indicating the string programmed into the robot.
It's guaranteed that the sum of nn of all test cases will not exceed (10^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
题意
给你一个x，y点和一个由UDLR组成的字符串，机器人从（0，0）位置开始走。
重排这个字符串使得机器人在走的过程中不会经过x,y
思路
x=0 && y=0的情况显然不合法。
先把起点和重点之间的路径抽象化成一个矩形，这样如果每一次走都把当前方向的步数走完的话到达终点就有24种情况。枚举(4!) 种情况 如果走到了雷上就返回false 如果有合法的方案就输出，否则的话就输出Impossible
刚开始我想自己手动枚举所有情况，写了快300行只过了三分之二的数据，于是考虑用next_permutation函数自动枚举每种情况。
代码(AC)
#include <bits/stdc++.h>
using namespace std;
string ans = "";
int x,y;
bool isok(char now[],int u,int d,int l,int r)
{
int cnt = 0;
int xx = 0,yy = 0;
ans = "";
for(int i=0; i<4; i++)
{
if(now[i] == 'U')
{
while(u--)
{
ans += 'U';
yy ++;
if(xx == x && yy == y) return false;
}
}
else if(now[i] == 'D')
{
while(d--)
{
ans += 'D';
yy --;
if(xx == x && yy == y) return false;
}
}
else if(now[i] == 'L')
{
while(l--)
{
ans += 'L';
xx --;
if(xx == x && yy == y) return false;
}
}
else if(now[i] == 'R')
{
while(r--)
{
ans += 'R';
xx ++ ;
if(xx == x && yy == y) return false;
}
}
}
return true;
}
void Solve()
{
scanf("%d%d",&x,&y);
string s;
cin>>s;
if(x==0 && y==0)
{
printf("Impossible");
return;
}
int len = s.size();
int xx = 0,yy = 0;
int u=0,d=0,l=0,r=0;
for(int i=0; i<len; i++)
{
if(s[i] == 'U') u++;
else if(s[i] == 'D') d++;
else if(s[i] == 'L') l++;
else r++;
}
int f = 0;
char ch[] = {'U','D','L','R'};
for(int i=0; i<24; i++)
{
if(isok(ch,u,d,l,r))
{
cout<<ans;
f = 1;
break;
}
next_permutation(ch,ch+4);
}
if(!f) cout<<"Impossible";
}
int main()
{
int t;
cin>>t;
while(t--)
{
Solve();
if(t) puts("");
}
}
代码(首次尝试)
#include <bits/stdc++.h>
using namespace std;
void Solve()
{
int x,y;
scanf("%d%d",&x,&y);
string s;
cin>>s;
if(x==0 && y==0)
{
printf("Impossible");
return;
}
int len = s.size();
int xx = 0,yy = 0 , f = 1;
int u=0,d=0,l=0,r=0;
int ok = 0;
for(int i=0; i<len; i++)
{
if(s[i] == 'U') yy++ , u++;
else if(s[i] == 'D') yy-- , d++;
else if(s[i] == 'L') xx-- , l++;
else xx++ , r++;
if(xx == x && yy == y)
f = 0;
}
if(f) cout<<s;
else if(xx == x && yy == y) printf("Impossible");
else if(l==0 && r==0)
{
if(x !=0 )
{
while(u--) printf("U");
while(d--) printf("D");
}
else
{
if(y>0)
{
if(u-d>=y)
printf("Impossible");
else
{
while(d--) printf("D");
while(u--) printf("U");
}
}
else
{
if(d-u>=abs(y))
printf("Impossible");
else
{
while(u--) printf("U");
while(d--) printf("D");
}
}
}
}
else if(u==0 && d==0)
{
if(y !=0 )
{
while(l--) printf("L");
while(r--) printf("R");
}
else
{
if(x>0)
{
if(r-l>=x)
printf("Impossible");
else
{
while(l--) printf("L");
while(r--) printf("R");
}
}
else
{
if(l-r>=abs(y))
printf("Impossible");
else
{
while(r--) printf("R");
while(l--) printf("L");
}
}
}
}
else // 三个以上不是0
{
int now_x = 0,now_y = 0;
int uu = u,dd = d,ll = l,rr = r;
int f = 0;
while(uu--)
{
now_y++;
if(now_x==x && now_y==y)
{
f = 1;
now_y--;
uu++;
break;
}
}
if(f) // 向上走遇到雷
{
if(xx!=0) //如果左右偏移不是0
{
ok = 1;
while(l--) printf("L");
while(r--) printf("R");
while(u--) printf("U");
while(d--) printf("D");
}
else // 如果左右偏移是0
{
if(yy!=y)
{
ok = 1;
while(l--) printf("L");
while(u--) printf("U");
while(d--) printf("D");
while(r--) printf("R");
}
else
{
printf("Impossible");
}
}
}
else // 向上走没遇到雷
{
while(dd--) // 向上走再向下走
{
now_y--;
if(now_x==x && now_y==y)
{
f = 1;
now_y++;
dd++;
break;
}
}
if(f) // 向上走再向下走遇到雷
{
if(xx!=0) // 横向偏移不是0 直接走
{
ok = 1;
while(l--) printf("L");
while(r--) printf("R");
while(u--) printf("U");
while(d--) printf("D");
}
else // 横向偏移是0 考虑U和
{
if(yy!=y)
{
ok = 1;
while(l--) printf("L");
while(u--) printf("U");
while(d--) printf("D");
while(r--) printf("R");
}
else
{
printf("Impossible");
}
}
}
else // 向上走向下走没有遇到雷-------------------------------------------------------------------
{
// 先左走
now_x = 0,now_y = 0;
int uu = u,dd = d,ll = l,rr = r;
int f = 0;
while(ll--)
{
now_x--;
if(now_x==x && now_y==y)
{
f = 1;
now_x++;
ll++;
break;
}
}
if(f) // 向左走遇到雷
{
if(yy!=0) //如果上下偏移不是0
{
ok = 1;
while(u--) printf("U");
while(d--) printf("D");
while(l--) printf("L");
while(r--) printf("R");
}
else // 如果上下偏移是0
{
if(xx!=x)
{
ok = 1;
while(u--) printf("U");
while(l--) printf("L");
while(r--) printf("R");
while(d--) printf("D");
}
else
{
printf("Impossible");
}
}
}
else // 往左走没遇到雷
{
while(rr--) // 往左走再往右走
{
now_x++;
if(now_x==x && now_y==y)
{
f = 1;
now_y--;
rr++;
break;
}
}
if(f) // 往左走再往右走
{
if(yy!=0) // 纵向偏移不是0 直接走
{
ok = 1;
while(u--) printf("U");
while(d--) printf("D");
while(l--) printf("L");
while(r--) printf("R");
}
else // 纵向偏移是0
{
if(xx!=x)
{
while(u--) printf("U");
while(l--) printf("L");
while(r--) printf("R");
while(d--) printf("D");
}
else
{
printf("Impossible");
}
}
}
else
{
while(u--) printf("U");
while(d--) printf("D");
while(l--) printf("L");
while(r--) printf("R");
}
}
}
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
Solve();
if(t) puts("");
}
}