P1686 挑战

    • 16通过
    • 54提交
  • 题目提供者 yeszy 管理员
  • 评测方式 云端评测
  • 标签 模拟 贪心 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    桃花岛其实也没什么好玩的,黄蓉经常偷偷跑到江湖上与洪七公等人玩。于是,黄药师就经常想一些游戏与女儿玩,为了是把黄蓉留在身边,江湖险恶啊!

    这次黄药师又想了一种模拟游戏,游戏是这样的:她把整个桃花岛划分成一个坐标系。游戏开始前,黄蓉站在平面坐标系的一个点上,而她的闺房在坐标系的另一个点上,任何时候,她可以从当前所在点跨一步达到她周围的上、下、左、右四个点,黄药师不断地说四个字“东(E)”、“南(S)”、“西(W)”、“北(N)”,则黄蓉就想象着不断地从一个点走到另一个点,直至到自己的闺房为止。

    [PIC=472]

    比如,黄蓉开始时站在A点,她的家在B点,黄药师连续说了一串:NNNENNWWWSSW,则走了如下一个线路。然后,黄药师会问黄蓉:中间有没有走“弯路”了?即有没有捷径好走?比如,下图中就有多条捷径,可以从C走NN而到E,或走WW直接到D。

    注意:捷径必须是直线。

    黄药师听说你是一个程序设计高手,就想请你编个程序帮他测测这个游戏的难度,以便改进游戏规则后再让黄蓉挑战。

    你的任务是:找一条最短的捷径。

    输入输出格式

    输入格式:

    第一行是一个整数n(3<=n<=250000)表示黄药师所报出的字符串长度。

    第二行是一个由N、E、S、W组成的字符串,都是大写字母且中间没有空格。

    我们把游戏的起点记为0,把黄蓉的闺房(即游戏的终点)记为n,中间的每一个落脚点都依次标记一个自然数。

    输出格式:

    输出只有一行,由3个数字和1个字符组成,中间用1个空格隔开。

    第1个数字表示最短捷径的长度。

    第2个数字表示最短捷径的开始点。

    第3个数字表示最短捷径的结束点。

    最后一个字符表示最短捷径的方向(同样用N、E、S、W中的一个表示)。

    如果最短捷径存在多个解,那么输出开始点标号最小的那一条。如果仍然有多个解,那么输出结束点标号最大的。数据保证一定存在满足条件的最短捷径。

    输入输出样例

    输入样例#1: 复制
    12
    NNNENNWWWSSW
    
    输出样例#1: 复制
    2 3 11 W
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。