#P9626. [ICPC 2020 Nanjing R] Evil Coordinate
[ICPC 2020 Nanjing R] Evil Coordinate
Description
一个机器人站在一个无限的二维平面上。它被编程为一个长度为 的字符串 ,其中 $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$,机器人将从 开始移动,并按照字符串中的字符指令进行移动。
更正式地说,设 为机器人的当前位置。机器人从 开始,重复以下过程 次。在第 次时:
- 如果 ,机器人从 移动到 ;
- 如果 ,机器人从 移动到 ;
- 如果 ,机器人从 移动到 ;
- 如果 ,机器人从 移动到 。
然而,在坐标 下埋有一个地雷。如果机器人在移动过程中踩到 ,它将被炸成碎片。可怜的机器人!
你的任务是重新排列字符串中的字符,使得机器人不会踩到 。
Input Format
有多个测试用例。输入的第一行包含一个整数 ,表示测试用例的数量。对于每个测试用例:
第一行包含两个整数 和 (),表示地雷的坐标。
第二行包含一个字符串 ,长度为 (, $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$),表示编程到机器人中的字符串。
保证所有测试用例的 的总和不超过 。
Output Format
对于每个测试用例输出一行。如果存在有效答案,打印重新排列后的字符串,否则打印 "Impossible"。如果有多个有效答案,可以打印其中任意一个。
5
1 1
RURULLD
0 5
UUU
0 3
UUU
0 2
UUU
0 0
UUU
LDLRUUR
UUU
Impossible
Impossible
Impossible
Hint
题面翻译由 ChatGPT-4o 提供。
京公网安备 11011102002149号