欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 1763 Shortcut G++ 模拟

程序员文章站 2022-07-15 11:02:16
...

POJ 1763 Shortcut G++ 模拟

POJ 1763 Shortcut G++ 模拟

POJ 1763 Shortcut G++ 模拟

#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;
}