C - Wandering Robot

比眉伴天荒 2022-01-30 08:07 137阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70 1]  
**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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]: /images/20220130/f670163d47e345889428777c2b1587bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70 1]: /images/20220130/59a2342c16994274a2ae72cc9ab226f2.png