C - Wandering Robot-蒲公英云

C - Wandering Robot

在这里插入图片描述

在这里插入图片描述
Sample Input

2
3 3
RUL
1 1000000000
D

Sample Output

4
1000000000

Hint

For the first sample test case, the final instruction sequence is “RULRULRUL” and the route of the robot is (0, 0) - (1, 0) - (1, 1) - (0, 1) - (1, 1) - (1, 2) - (0, 2) - (1, 2) - (1, 3) - (0, 3). It’s obvious that the farthest point on the route is (1, 3) and the answer is 4.

题意：U D L R分别表示向上走，向下走，向左走，向右走。
给你一串UDLRDU…（指定方向图），让你循环k次，问你这期间距离原点最远是多少。

思路，先让它循环一次，找出最大值，然后找出他第一次循环完的那个点，平移（n-1）次，再以平移后的点为原点，在循环一次操作，找出一个最大值，距离原点最远的值必定出现在第一次循环和最后一次循环。

AC代码：

#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,m;
        string s;
        cin>>n>>m;
        cin>>s;
        ll mmax=0;
        ll x=0,y=0;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='U')
                y++;
            else if(s[i]=='D')
                y--;
            else if(s[i]=='L')
                x--;
            else if(s[i]=='R')
                x++;
            mmax=max(mmax,abs(x)+abs(y));    
        }
        x*=(m-1);
        y*=(m-1);
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='U')
                y++;
            else if(s[i]=='D')
                y--;
            else if(s[i]=='L')
                x--;
            else if(s[i]=='R')
                x++;
            mmax=max(mmax,abs(x)+abs(y));    
        }
        cout<<mmax<<endl;
            }
    return 0;
}