Codeforces Round #389 Div.2 C. Santa Claus and Robot

time limit per test

2 seconds

Santa Claus has Robot which lives on the infinite grid and can move along its lines. He can also, having a sequence of m pointsp1, p2, ..., pm with integer coordinates, do the following: denote its initial location by p0. First, the robot will move from p0 to p1 along one of the shortest paths between them (please notice that since the robot moves only along the grid lines, there can be several shortest paths). Then, after it reaches p1, it'll move to p2, again, choosing one of the shortest ways, then to p3, and so on, until he has visited all points in the given order. Some of the points in the sequence may coincide, in that case Robot will visit that point several times according to the sequence order.

While Santa was away, someone gave a sequence of points to Robot. This sequence is now lost, but Robot saved the protocol of its unit movements. Please, find the minimum possible length of the sequence.

Input

The first line of input contains the only positive integer n (1 ≤ n ≤ 2·105) which equals the number of unit segments the robot traveled. The second line contains the movements protocol, which consists of n letters, each being equal either L, or R, or U, or D. k-th letter stands for the direction which Robot traveled the k-th unit segment in: L means that it moved to the left, R — to the right, U — to the top and D — to the bottom. Have a look at the illustrations for better explanation.

Output

The only line of input should contain the minimum possible length of the sequence.

Examples

input

4
RURD

output

input

6
RRULDD

output

input

26
RRRULURURUULULLLDLDDRDRDLD

output

input

3
RLL

output

input

4
LRLR

output

思考可以发现，一段连续的操作序列中如果没有方向相反的指令，就可以用一个点确定线路，否则需要添加一个新点。

做题的时候想得有点复杂，模拟了一个坐标系，满足当前距离到上个路径点的距离不递减时，一直走，否则新建一个路径点。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 const int mxn=200100;
 8 int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}
12     return x*f;
13 }
14 int n;
15 char s[mxn];
16 int lx,ly,sx,sy;
17 int px,py;
18 int dist(){
19     return abs(px-sx)+abs(py-sy);
20 }
21 int main(){
22     n=read();
23     scanf("%s",s);
24     int i,j;
25     int len=strlen(s);
26     int last=0,ans=0;
27     lx=ly=px=py=sx=sy=0;
28     bool flag=0;
29     for(i=0;i<len;i++){
30 //        printf("%c
",s[i]);
31         switch(s[i]){
32             case 'U':{px--;    break;}
33             case 'R':{py++;    break;}
34             case 'D':{px++; break;}
35             case 'L':{py--;    break;} 
36         }
37         int now=dist();
38         if(now<last){
39             sx=lx;sy=ly;
40             ans++;
41             last=0;
42             i--;
43             continue;
44         }
45         last=now;
46         lx=px;ly=py;
47     }
48     cout<<ans+1<<endl;
49     return 0;
50 }