[Usaco2016 Jan] Build Gates
时间限制：10s 空间限制：128MB
题目描述
Farmer John decides to build a new fence around parts of his farm, but he keeps getting distracted a
nd ends up building the fence into a much stranger shape than he intended!Specifically, FJ starts at
position (0,0)and takes N steps, each moving one unit of distance north, south, east, or west. Each
step he takes, he lays a unit of fence behind him. For example, if his first step is to the north,
he adds a segment of fence from (0,0) to (0,1). FJ might re-visit points multiple times and he may e
ven lay the same segment of fence multiple times. His fence might even cross over itself if his path
cuts through a run of fencing he has already built.Needless to say, FJ is rather dismayed at the re
sult after he completes the fence. In particular, he notices that it may be the case that he has now
partitioned off some areas of the farm from others, so that one can no longer walk from one region
to another without crossing a fence. FJ would like to add gates to his fences to fix this problem. A
gate can be added to any unit-length segment of fence he has built, allowing passage between the tw
o sides of this segment.Please determine the minimum number of gates FJ needs to build so that every
region of the farm is once again reachable from every other region.
给定一个包含N,S,E,W的移动序列。FJ初始在(0,0)，依次按照移动序列移动，并在移动过程中建设篱笆。如FJ在(0
,0)点，要向N移动，则FJ移动到(0,1)，并在(0,0)和(0,1)之间建一段篱笆。注意到这样建设出的篱笆可能自交，
把平面划分成若干区域。现在要拆除若干段篱笆，使平面连通。输出最少拆除的篱笆段数。1 ≤ N ≤ 1000
输入格式
The first line of input contains N(1≤N≤1000). The next line contains a string of length N
describing FJ's path. Each character is either N (north), E (east), S (south), or W (west).
输出格式
Write out a single integer giving the minimum number of gates FJ needs to build to restore complete connectivity to all regions of his farm. Note that the answer could be zero if the farm is connected to begin with.
样例输入
14 NNNESWWWSSEEEE
样例输出
2
提示
没有写明提示
题目来源
Silver鸣谢frank_c1提供翻译