Build Gates

题目描述

农夫约翰决定在他的农场部分区域周围建一圈新围栏，但他总是分心，结果把围栏修成了一个比原计划奇怪得多的形状！

具体来说，FJ 从位置 $(0,0)$ 出发，走 $N$ 步，每一步都向北、南、东或西移动 1 个单位距离。每走一步，他就在身后铺设一段长度为 1 的围栏。例如，如果他的第一步向北，那么他会添加一段从 $(0,0)$ 到 $(0,1)$ 的围栏线段。FJ 可能会多次回到同一个点，甚至可能多次铺设同一段围栏。如果他的路径穿过了他已经建好的围栏线段序列，他的围栏甚至可能与自身交叉。

不必说，FJ 在完成围栏后对结果非常沮丧。特别地，他注意到：现在可能已经把农场划分成若干区域，使得不跨越围栏就无法从一个区域走到另一个区域。FJ 想在围栏上加一些门来解决这个问题。一扇门可以加在他建过的任意一段单位长度围栏上，从而允许在该线段两侧之间通行。

请确定 FJ 需要建造的最少门数，使得农场的每个区域都能再次从其他任意区域到达。

输入格式

第一行输入 $N$（$1 \leq N \leq 1000$）。第二行包含一个长度为 $N$ 的字符串，描述 FJ 的路径。每个字符是 N（北）、E（东）、S（南）或 W（西）。

输出格式

输出一个整数，表示 FJ 需要建造的最少门数，以恢复农场所有区域之间的完全连通性。注意：如果农场一开始就是连通的，那么答案可能为 0。

14
NNNESWWWSSEEEE

2

提示

题目来源：Brian Dean

标签: USACO|2016|Silver

来源

USACO|2016|Silver