A2824 | $Build Gates S$

来源USACO / 2016

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出