Mirek has a favourite way from home to the university that he traverses every working day. The route consists of sections and each section is a straight segment 10 meters long. Each section is either a straight ahead extension of the previous section or it is perpendicular to the previous section. After traversing each section Mirek takes a small break to admire the beauty of the nature. During his walk he never visits the same place twice.
Yesterday Mirek stayed up long in the night at the party and today he got up late from bed. He knows that he will miss the first lecture unless he changes his usual route. He plans to make one shortcut but he wants the shortcut to be as short as possible (well, we can tell you in secret that he doesn’t want to be on time, he just wants to calm his conscience). The shortcut must be either a horizontal or vertical segment connecting two break points of Mirek’s route.
Please help Mirek find the shortest shortcut.
Task Write a program that:
reads Mirek’s route, computes the shortest shortcut on the route, writes the result.
Input
The first line of the input contains one integer n (3 <= n <= 250 000) being the number of sections of the route. The second line of the input contains a sequence of n characters N, E, S or W with no spaces in between. Each character is a description of one section of the route. Character N, E, S or W means that Mirek walks 10 meters north, east, south or west respectively. You may assume that at least one shortcut exists for the given route.
Output
The first and only line of the output contains integers l, b, e and character d separated by single spaces. Integer l is the length of the shortest shortcut (measured in 10 m segments). Integers b and e are the numbers of break points where the shortcut begins and ends respectively (we number break points with consecutive integers from 0 for Mirek’s home to n for the university). Character d is the direction of the shortcut. If more than one shortcut of the minimal length exists you should output the one that begins earliest on the route. If more than one shortcut of the minimal length begins at the same break point you should output the one that ends furthest on the route.
Sample Input
12 NNNENNWWWSSW
Sample Output
2 3 11 W
方法根据题意我们可以得出两条结论：
第一，我们可以得知捷径只有两种情况，要么水平要么垂直。（设捷径由路径上两个点p1,p2构成。如果捷径是水平的，则两个点的y坐标相同，反之，如果是垂直的，则两个点的x坐标相同。）第二，构成捷径的两个点的编号肯定不相邻（如果相邻，则两个点之间的连线属于路径的一部分）。解题步骤：
输入n个线段方向后，构造出n+1个点，Mirek的家定义为原点(0,0)。初始时，令x=y=0。如果当前点的方向为’N’，则y++，如果方向为’S’，则y–，'E’和’W’分别使x++，x–，判断完方向后可以得到走过的坐标。
首先我们对垂直方向找最优捷径，对所有n+1个点按x坐标从小到大排序，如果x坐标相等则按y坐标从小到大排序。 顺序扫描数组，将x坐标相同的点看成一组，如果某个组中的点数大于1，则它们之间有可能存在捷径。
考虑每一个点数大于1的组，从左到右扫描，y坐标依次增大。
如果相邻两点编号相同，则该两点之间不存在捷径，反之，则该相邻两点存在捷径。
当找到一个捷径时，计算它的长度len，开始节点编号b，结束节点编号e，方向d，如果该捷径比已经找到的捷径更优，则更新最优捷径。（最优的标准依次为长度最短，长度相等情况下开始节点编号最小，前两种情况均相等时结束节点编号最大）
找水平方向的最优捷径。即：将所有点的x，y坐标互换，则转换为求垂直方向的最优捷径，重复利用第2步。
AC代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int MAXN = 250010; struct Node { int x,y; int num; }; Node *node; int n; char str[MAXN]; int ans_l=MAXN,ans_b,ans_e; char ans_c; bool compare(Node a,Node b) { if(a.x != b.x) { return a.x<b.x; } return a.y<b.y; } int fun(char c1,char c2) { for(int i=0;i<n;i++) { int len,b,e,c; if(node[i].x==node[i+1].x && abs(node[i+1].num-node[i].num)>1) { len = node[i+1].y-node[i].y; //根据编号确定起始点，终点，以及方向 if(node[i].num<node[i+1].num) { b = node[i].num; e = node[i+1].num; c = c1; } else { b = node[i+1].num; e = node[i].num; c = c2; } //如果存在多个最小长度的快捷方式，则应输出最早在路径上开始的快捷方式。 //如果最小长度的多个快捷方式从同一个断点开始，则应输出在路径上最远的那个。 if(ans_l>len || (ans_l==len && ans_b>b) || (len==ans_l&&b==ans_b&&e>ans_e)) { ans_l = len; ans_b = b; ans_e = e; ans_c = c; } } } return 0; } int main() { int x=0,y=0; scanf("%d",&n); scanf("%s",str); node = new Node[n+1]; node[0].num = node[0].x = node[0].y = 0; for(int i=0;i<n;i++) { node[i+1].num = i+1; switch(str[i]) { case 'N': y++; break; case 'E': x++; break; case 'S': y--; break; case 'W': x--; break; } node[i+1].x = x; node[i+1].y = y; } sort(node,node+n+1,compare); //判断垂直上的捷径 fun('N','S'); int temp; //交换x,y for(int i=0;i<=n;i++) { temp=node[i].x; node[i].x = node[i].y; node[i].y = temp; } sort(node,node+n+1,compare); //判断水平上的捷径 fun('E','W'); printf("%d %d %d %c\n",ans_l,ans_b,ans_e,ans_c); return 0; }