Santa Claus has Robot which lives on the infinite grid and can move
along its lines. He can also, having a sequence of m points
p1,?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.
InputThe 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. OutputThe only line of input should contain the minimum possible length of
the sequence.
贪心地走，直到走了回头路说明必须要新开一段。
#include<cstdio>
#include<cstring>
char s[200010];
bool b[10];
int d[1000];
int main()
{int n,i,ans;scanf("%d%s",&n,s+1);ans=0;d['L'-'A'+1]=0;d['U'-'A'+1]=1;d['D'-'A'+1]=2;d['R'-'A'+1]=3;for (i=1;i<=n;i++){if (b[3-d[s[i]-'A'+1]]){ans++;b[0]=b[1]=b[2]=b[3]=0;}b[d[s[i]-'A'+1]]=1;}printf("%d\n",ans+1);
}