[USACO16JAN] Build Gates S
题目描述
FarmerJohn 打算在他农场的一部分,建设一个围栏。但是因为没有认真做事,建造完成后,围栏变成一个很奇怪的形状。
具体来说,FJ 从 $(0,0)$ 出发,走了 $N$ 步,每步移动一单位(向东、向南、向西或向东)。
他走过的每一步,都会留下一段单位长度的围栏。例如,如果他的第一步向北,他建造一单位从 $(0,0)$ 到 $(0,1)$ 的围栏。
FJ 可能重复到达点多次,他也可能重复建造一段围栏多次。如果他的路径穿过一段已经建成的围栏,他的围栏也有可能会有交叉。
不用说,FJ 看到完成的围栏时,一定很沮丧。特别的,他发现一些区域被围栏封闭起来,从而无法到达。FJ 想在围栏上,安装一些门来解决这个问题。
门可以安装在任意一段单位长度(注:必须是之前走过的某一步)的围栏上,从而可以穿越这段围栏的两侧。
请计算 FJ 最少需要安装多少个门,才能保证农场上任意区域到任意区域都可到达。
输入输出格式
输入格式
第一行一个整数 $N$。
第二行包含一个长度为 $N$ 的字符串,描述 FJ 的路径。每个字符为 $\tt N$(北),$\tt E$(东),$\tt S$(南),或 $\tt W$(西)。
输出格式
输出一个整数,表示为了保证农场所有区域的连通性,FJ 最少需要安装多少个门。
输入输出样例
输入样例 #1
14
NNNESWWWSSEEEE
输出样例 #1
2
说明
注意,如果农场初始连通,答案就是 $0$。
### 数据范围
$1\le n\le 1000$。