P2771 [USACO16Jan]建门 gates

    • 81通过
    • 240提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 字符串 USACO 2016
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

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

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

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

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

    输入输出格式

    输入格式:

    1行:包含N。

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    14
    NNNESWWWSSEEEE
    输出样例#1: 复制
    2

    说明

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

    [数据范围]

    n<=1000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。