Skip to content

14173: 【原4173】robot

题目

题目描述

author: cyx666 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4173 ## Description

现有一个机器人在一个无穷大的平面直角坐标系上,从\((0,0)\)开始,按如下指令移动: U — \((x,y)\) => \((x,y+1)\); D — \((x,y)\) => \((x,y−1)\); L — \((x,y)\) => \((x−1,y)\); R — \((x,y)\) => \((x+1,y)\)。 给定一段指令序列和目标坐标\((x,y)\),并允许改变其中连续一段指令,使得机器人能够按改动后的指令到达目标坐标,问最小修改长度。 若无法到达,则输出\(-1\)。

Input Format

第一行包含一个正整数n,表示指令序列长度; 第二行包含一个长度为n的字符串,表示指令序列; 第三行包含两个整数x和y,表示目标坐标。

Output Format

一个整数,表示最小修改长度或无法修改。

Sample Input1

5
RURUU
-2 3

Sample Output1

3

Sample Input2

3
UUU
100 100

Sample Output2

-1

Data Range

对于30%的数据,\(1 \le n \le 1000\)

对于60%的数据,\(1 \le n \le 2*10^5\)

对于100%的数据,\(1 \le n \le 4*10^6\),\(1 \le x,y \le 10^9\)

WashSwang's solution

#include <iostream>
using namespace std;
int x,y,ans,n,head,rear=-1,c,s[5000000];
long long tol[4];
int parse(int c){
    if (c=='U') return 0;
    if (c=='D') return 1;
    if (c=='L') return 2;
    return 3;
}
inline bool check(long long x){
    return (x>=0)&&(x%2==0);
}
inline long long dist(){
    return abs(x-(tol[3]-tol[2]))+abs(y-(tol[0]-tol[1]));
}
int main() {
    scanf("%d",&n);
    ans=n+1;
    getchar();
    for (int i=0;i<n;++i){
        c=getchar();
        s[i]=parse(c);
        tol[parse(c)]++;
    }
    scanf("%d%d",&x,&y);
    for (int i=0;i<n;++i){
        tol[s[++rear]]--;
        while (check((rear-head+1)-dist())&&head<=rear){
            if (rear-head+1<ans) ans=rear-head+1;
            tol[s[head++]]++;
        }
    }
    if (ans==n+1) printf("-1");
    else printf("%d",ans);
    return 0;
}