E-Evil Coordinate（模拟）

alt alt

输入样例

5
1 1
RURULLD
0 5
UUU
0 3
UUU
0 2
UUU
0 0
UUU

输出样例

LDLRUUR
UUU
Impossible
Impossible
Impossible

题解

需要注意一件事，就是无论怎么安排机器人所走的路径，那么他的最终所到达的点是相同的。

我总共分了三种情况：

当炸弹在原点的时候，那么就不能避免
当炸弹在坐标轴（非原点）的时候
当炸弹不在坐标轴的时候

对于第2种情况

如果在 x 轴上，那么

没有U和D，那么就只有L，R。我需要尽可能地朝炸弹反方向走，然后迫不得已向炸弹移动。
如果有U和D，那么如果U==D，那么就会离开坐标轴，然后回来。如果对于最终机器人走到的点的坐标如果与炸弹的横坐标相同，那么就寄了，否则先离开坐标轴，然后再左右移动，最终回到坐标轴。
如果有U和D，并且U!=D，那么先上下走，离开坐标轴，然后再左右走。

对于第3种情况

如果最终走到的点的横坐标与炸弹的横坐标不相同，那么先左右走，再上下走。
如果最终走到的点的横坐标与炸弹的横坐标相同，那么先上下，再左右。

我通过了对于炸弹在坐标轴以及不在坐标轴上的情况进行分类讨论，最终简化了问题。

代码

#include <bits/stdc++.h>
using namespace std;
#define N 100020
char a[N];
int mx, my;
void Print(char x, int num)
{
    for(int i = 1; i <= num; i++) 
        putchar(x);
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &mx, &my);
        scanf("%s", a+1);
        int len = strlen(a+1);
        int U, L, R, D;
        U = L = R = D = 0;
        for(int i = 1; i <= len; i++)
        {
            switch (a[i])
            {
            case 'U':
                U++;
                break;
            case 'R':
                R++;
                break;
            case 'D':
                D++;
                break;
            case 'L':
                L++;
                break;
            }
        }
        int endx = R-L;
        int endy = U-D;
        if(mx == 0 && my == 0){//原点
            puts("Impossible");
        }
        else if(mx == 0 || my == 0)//坐标轴
        {
            if(my == 0)//x周
            {
                if(U == 0 && D == 0)
                {
                    if(mx < 0){
                        if(endx <= mx){
                            puts("Impossible");
                        }
                        else{
                            Print('R', R);
                            Print('L', L);
                            puts("");
                        }
                    }
                    else if(mx > 0){
                        if(endx >= mx){
                            puts("Impossible");
                        }
                        else{
                            Print('L', L);
                            Print('R', R);
                            puts("");
                        }
                    }
                }
                else if(U == D){
                    if(endx == mx) puts("Impossible");
                    else{
                        Print('U', U), Print('L', L), Print('R', R), Print('D', D);
                        puts("");
                    }
                }
                else{
                    Print('U', U), Print('D', D), Print('R', R), Print('L', L);
                    puts("");
                }
            }
            if(mx == 0)//y轴
            {
                if(L == 0 && R == 0)
                {
                    if(my < 0){
                        if(endy <= my){
                            puts("Impossible");
                        }
                        else{
                            Print('U', U);
                            Print('D', D);
                            puts("");
                        }
                    }
                    else if(my > 0){
                        if(endy >= my){
                            puts("Impossible");
                        }
                        else{
                            Print('D', D);
                            Print('U', U);
                            puts("");
                        }
                    }
                }
                else if(L == R){
                    if(endy == my) puts("Impossible");
                    else{
                        Print('L', L), Print('U', U), Print('D', D), Print('R', R);
                        puts("");
                    }
                }
                else{
                    Print('L', L), Print('R', R), Print('U', U), Print('D', D);
                    puts("");
                }
            }
        }
        else 
        {
            if(mx == endx && my == endy)
            {
                puts("Impossible");
            }
            else
            {
                if(endx != mx){
                    Print('L', L), Print('R', R), Print('U', U), Print('D', D);
                    puts("");
                }
                else if(endx == mx){
                    Print('U', U), Print('D', D), Print('L', L), Print('R', R);
                    puts("");
                }
            }
        }
    }
    return 0;
}

题解 | #Evil Coordinate#

E-Evil Coordinate（模拟）

题解

代码