Codeforces Round #617 (Div. 3)-C. Yet Another Walking Robot(STL)

题目链接:C. Yet Another Walking Robot

题目大意: 有个机器人起始在(0,0),给出一个字符串S(行动序列),其中包含四个字母,'U’表示向上;'D’表示向下;'L’表示向左;'R’表示向右。要求在S中找个子串,使在执行子串操作后,机器人的位置不变,要求所求子串的长度最小,并且输出左右边界下标。

解题思路: 根据题意,遍历字符串S进行移动,我们只需要记录每个坐标所对应的子串下标,第二次走到某个坐标时,就代表从之前这个坐标开始走到现在位置是不变的,注意还要更新这个坐标的下标。那么实现存储坐标,我使用了map<pair<int,int>,int>m,pair<int,int>存储坐标,int表示下标位置。插入方法就是m[{x,y}]=下标位置。

代码:

#include <bits/stdc++.h>
using namespace std;
char s[200010];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        scanf("%s",s+1);
        map<pair<int,int>,int>m;
        int x=0,y=0;
        int mi=1e9;
        int l=0,r=0;
        m[{0,0}]=1;
        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 if(s[i]=='D'){
                y--;
            }
            if(m[{x,y}]){
                if(mi>i-m[{x,y}]+1){
                    l=m[{x,y}];
                    r=i;
                    mi=r-l+1;
                }
            }
                m[{x,y}]=i+1;
        }
        if(mi==1e9){
            cout<<-1<<endl;
        }else{
            cout<<l<<" "<<r<<endl;
        }
    }
    return 0;
}
Codeforces Round #617 (Div. 3)-C. Yet Another Walking Robot(STL)Codeforces Round #617 (Div. 3)-C. Yet Another Walking Robot(STL) 182cx 发布了31 篇原创文章 · 获赞 2 · 访问量 647 私信 关注
上一篇:浏览器回退出现ERR_CACHE_MISS 解决方案


下一篇:Yet Another Walking Robot