題意大概是這樣，如上圖所示，粗線描述的是一個(gè)人從家到學(xué)校的網(wǎng)格圖上的路徑，現(xiàn)在他想找一條捷徑，shortcut，即兩端都在路徑頂點(diǎn)上且不與任何一條路徑相交，問最短的捷徑為多長(zhǎng)。如果有重復(fù)，則要求起點(diǎn)編號(hào)盡量小，如果再重復(fù)，則終點(diǎn)編號(hào)盡量大。
這題要分別統(tǒng)計(jì)水平捷徑和垂直捷徑。以統(tǒng)計(jì)水平捷徑為例：
1、對(duì)所有點(diǎn)的y坐標(biāo)進(jìn)行離散化（不離散化統(tǒng)計(jì)的時(shí)候hash也行。。）
2、對(duì)所有點(diǎn)坐標(biāo)以x坐標(biāo)降序排列
3、對(duì)點(diǎn)進(jìn)行掃描，判斷當(dāng)前點(diǎn)的y值是否在hash表內(nèi)（即判斷該點(diǎn)右側(cè)是否有路徑節(jié)點(diǎn)），如果存在的話用hash表中記錄的前一個(gè)x值與當(dāng)前點(diǎn)的x值作差，然后與當(dāng)前最小值比較，如果小于當(dāng)前最小值，則更新節(jié)點(diǎn)；然后更新hash表中的值為當(dāng)前點(diǎn)的x值
剩下的就是細(xì)節(jié)的處理了- -
貼代碼（nlogn跑了1s多，有點(diǎn)不爽）
1 # include <cstdio>
2 # include <algorithm>
3 # include <cstring>
4 using namespace std;
5 struct node
6 {
7 bool r,u;
8 int x,y;
9 int mapx,mapy;
10 int pos;
11 }data[250005];
12 bool cmpx(const node &a,const node &b)
13 {
14 return a.x>b.x;
15 }
16 bool cmpy(const node &a,const node &b)
17 {
18 return a.y>b.y;
19 }
20 char str[250005];
21 int id[250005];
22 int len;
23 int main()
24 {
25 scanf("%d",&len);
26 scanf("%s",str);
27 len++;
28 int x=0,y=0;
29 for(int i=0;i<len;i++)
30 data[i].u=data[i].r=1;
31 for(int i=0;i<len-1;i++)
32 {
33 data[i].x=x;
34 data[i].y=y;
35 data[i].pos=i;
36
37 switch(str[i])
38 {
39 case 'N':
40 y++;
41 data[i].u=0;
42 break;
43 case 'E':
44 data[i].r=0;
45 x++;
46 break;
47 case 'S':
48 data[i+1].u=0;
49 y--;
50 break;
51 case 'W':
52 data[i+1].r=0;
53 x--;
54 break;
55 };
56 }
57 int res=0xfffffff,s,e;
58 char dir;
59 data[len-1].x=x;
60 data[len-1].y=y;
61 data[len-1].pos=len-1;
62 sort(data,data+len,cmpx);
63 data[len-1].mapx=0;
64 for(int i=len-2;i>=0;i--)
65 if(data[i].x==data[i+1].x)
66 data[i].mapx=data[i+1].mapx;
67 else
68 data[i].mapx=data[i+1].mapx+1;
69 sort(data,data+len,cmpy);
70 data[len-1].mapy=0;
71 for(int i=len-2;i>=0;i--)
72 if(data[i].y==data[i+1].y)
73 data[i].mapy=data[i+1].mapy;
74 else
75 data[i].mapy=data[i+1].mapy+1;
76 memset(id,-1,sizeof(id));
77 for(int i=0;i<len;i++)
78 {
79 if(id[data[i].mapx]!=-1&&data[i].u)
80 if(data[id[data[i].mapx]].y-data[i].y<res||data[id[data[i].mapx]].y-data[i].y==res&&min(data[id[data[i].mapx]].pos,data[i].pos)<s||data[id[data[i].mapx]].y-data[i].y==res&&min(data[id[data[i].mapx]].pos,data[i].pos)==s&&max(data[id[data[i].mapx]].pos,data[i].pos)>e)
81 {
82 res=data[id[data[i].mapx]].y-data[i].y,s=min(data[id[data[i].mapx]].pos,data[i].pos),e=max(data[id[data[i].mapx]].pos,data[i].pos);
83 if(data[i].pos<data[id[data[i].mapx]].pos) dir='N';
84 else dir='S';
85 }
86 id[data[i].mapx]=i;
87 }
88 sort(data,data+len,cmpx);
89 memset(id,-1,sizeof(id));
90 for(int i=0;i<len;i++)
91 {
92 if(id[data[i].mapy]!=-1&&data[i].r)
93 if(data[id[data[i].mapy]].x-data[i].x<res||data[id[data[i].mapy]].x-data[i].x==res&&min(data[id[data[i].mapy]].pos,data[i].pos)<s||data[id[data[i].mapy]].x-data[i].x==res&&min(data[id[data[i].mapy]].pos,data[i].pos)==s&&max(data[id[data[i].mapy]].pos,data[i].pos)>e)
94 {
95 res=data[id[data[i].mapy]].x-data[i].x,s=min(data[id[data[i].mapy]].pos,data[i].pos),e=max(data[id[data[i].mapy]].pos,data[i].pos);
96 if(data[i].pos<data[id[data[i].mapy]].pos)
97 dir='E';
98 else
99 dir='W';
100 }
101 id[data[i].mapy]=i;
102 }
103 printf("%d %d %d %c\n",res,s,e,dir);
104 return 0;
105 }
106