POJ 1763 Shortcut G++ 模拟
程序员文章站
2022-07-15 11:02:16
...
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
//英语 看博友分析 抄博友程序 模拟
struct nod{
int x;
int y;
int num;
}da[250010];
int n;
int l,s,e;
char d;
char str[250010];
bool cmp(nod a,nod b)
{
if(a.x==b.x)
{
return a.y<b.y;
}else
{
return a.x<b.x;
}
}
void fun(char c1,char c2)
{
for(int i=0;i<n;i++)//抄博友程序
{
int len;
int ts,te;
int td;
if(da[i].x==da[i+1].x&&abs(da[i].num-da[i+1].num)>1)//抄博友程序 背
{
len=da[i+1].y-da[i].y;//抄博友程序
if(da[i].num<da[i+1].num)
{
ts=da[i].num;
te=da[i+1].num;
td=c1;
}else
{
ts=da[i+1].num;
te=da[i].num;
td=c2;
}
if(l>len||(len==l&&ts<s)||(len==l&&ts==s&&te>e))//抄博友程序
{
l=len;
s=ts;
e=te;
d=td;
}
}
}
}
int main()
{
scanf("%d",&n);
scanf("%s",str);
int x=0;
int y=0;
da[0].x=0;
da[0].y=0;
da[0].num=0;
for(int i=0;i<n;i++)
{
if(str[i]=='N')
{
y++;
}else if(str[i]=='S')
{
y--;
}else if(str[i]=='W')
{
x--;
}else if(str[i]=='E')
{
x++;
}
da[i+1].x=x;
da[i+1].y=y;
da[i+1].num=i+1;
}
sort(da,da+n+1,cmp);
/*for(int i=1;i<=n;i++)
{
cout<<da[i].x<<" "<<da[i].y<<" ";
}
cout<<endl;*/
l=250010;
//cout<<l<<" -"<<s<<" -"<<e<<" -"<<d<<endl;
fun('N','S');
for(int i=0;i<=n;i++)
{
int t=da[i].x;
da[i].x=da[i].y;
da[i].y=t;
//swap(da[i].x,da[i].y);
}
sort(da,da+n+1,cmp);
fun('E','W');
printf("%d %d %d %c\n",l,s,e,d);
//cout<<l<<" +"<<s<<" +"<<e<<" +"<<d<<endl;
return 0;
}