捷径(Shortcut)

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 1

题目描述

Mirek 有一条每天从他家去大学工作的最喜欢的路。这个路径由若干个部分组成,且每个部分都是 1 单位长的直线。每一个部分都是直线连接(没有拐弯)上一个部分或垂直连接上一个部分。在走过每一个部分后,Mirek 会休息下欣赏美丽的自然景色。在他走路的过程之中,他不会重复访问一个地点。

昨天,Mirek 在 party 中熬夜到很迟,并且今天他迟起床了。他意识到他会错过第一堂课除非他改变他平时走的路径。他计划找一条捷径,但他希望捷径尽量的短。捷径必须是水平的或者是垂直的并且连接两个 Mirek 原先路径的休息的地点。

请帮助 Mirek 找到最短的捷径。

输入

第一行包含一个整数 n(3<=n<=250,000)作为路径的部分的个数。第二行包含一组长度为 n 的序列,每个字母为 N,E,S 或 W,之间没有空格。每一个字母描述路径的一个部分。字母 N,E,S 或 W 表示 Mirek 向这些方向走了 1 单位长。你可以假设至少存在一个捷径。

45%的数据:n<=1,000

100%的数据:n<=250,000

输出

仅一行,包括 L、B、E 三个整数和一个字母 D,用空格隔开。L 是最短的捷径的单位长度。B 和 E 是休息点的编号,也就是捷径的起点和终点(Mirek 的 home 的编号为 0,大学的编号为 n)。字母 D 是捷径的方向。如果有超过 1 条最短的捷径存在,你应该输出起点最小的;如果有多个起点相同的捷径,你应该输出终点编号最大的。

输入样例

12 
NNNENNWWWSSW 

输出样例

2 3 11 W 

Source

江苏省苏州中学 NOIP 复赛训练题 2012

相关推荐