C. Yet Another Walking Robot

C. Yet Another Walking Robot

题面

题意

给一个字符串，RLUD分别代表右左上下，机器人按给定的字符串移动，现要求你删掉字符中的某一个子串，且删掉后机器人仍然可以到达原终点，问该被删子串的最小长度，输出字串的开始位置与结束位置

思路

在纸上模拟了一下第一个样例

用map来记录点的坐标与到达时间（这里的时间用字符串的下标表示），如果出现了重复的点则更新最小值## AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>

using namespace std;

const int N = 2e5 + 10,INF=0x3f3f3f3f;
char s[N];
int n;
typedef pair<int, int> PII;
map<PII, int> mp;

int main()
{
    int t;
    for (cin >> t; t;t--)
    {
        cin >> n;
        cin >> (s + 1);
        mp.clear();
        int x = 0, y = 0;
        mp[PII(x, y)] = 0;
        int ans = INF;
        int l, r;

        for (int i = 1; i <= n;i++)
        {
            if(s[i]=='L')
                x--;
            else if(s[i]=='R')
                x++;
            else if(s[i]=='U')
                y++;
            else
                y--;
            PII temp = make_pair(x, y);
            if (mp.count(temp))
            {
                if (ans >i-mp[temp])
                {
                    ans = i - mp[temp];
                    l = mp[temp];
                    r = i;
                }
            }
            mp[temp] = i;
        }
        if(ans==INF)
            cout << "-1\n";
        else
            cout << l+1 << " " << r << endl;
    }
        return 0;
}