P9626 [ICPC2020 Nanjing R] Evil Coordinate 题解

WhitD · 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;
}