A22535.Build Gates S

普及/提高-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

FarmerJohn 打算在他农场的一部分,建设一个围栏。但是因为没有认真做事,建造完成后,围栏变成一个很奇怪的形状。

具体来说,FJ 从 (0,0)(0,0) 出发,走了 NN 步,每步移动一单位(向东、向南、向西或向东)。

他走过的每一步,都会留下一段单位长度的围栏。例如,如果他的第一步向北,他建造一单位从 (0,0)(0,0)(0,1)(0,1) 的围栏。

FJ 可能重复到达点多次,他也可能重复建造一段围栏多次。如果他的路径穿过一段已经建成的围栏,他的围栏也有可能会有交叉。

不用说,FJ 看到完成的围栏时,一定很沮丧。特别的,他发现一些区域被围栏封闭起来,从而无法到达。FJ 想在围栏上,安装一些门来解决这个问题。

门可以安装在任意一段单位长度(注:必须是之前走过的某一步)的围栏上,从而可以穿越这段围栏的两侧。

请计算 FJ 最少需要安装多少个门,才能保证农场上任意区域到任意区域都可到达。

输入格式

第一行一个整数 NN

第二行包含一个长度为 NN 的字符串,描述 FJ 的路径。每个字符为 N\tt N(北),E\tt E(东),S\tt S(南),或 W\tt W(西)。

输出格式

输出一个整数,表示为了保证农场所有区域的连通性,FJ 最少需要安装多少个门。

输入输出样例

  • 输入#1

    14
    NNNESWWWSSEEEE

    输出#1

    2

说明/提示

注意,如果农场初始连通,答案就是 00

数据范围

1n10001\le n\le 1000

首页