pku1763.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 149 行

#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxn = 250100;

typedef struct Point
{
	int x, y;
	int id;
}Point;

Point p[maxn];
char s[maxn];
int N;
int mindis;
char mindir;
int start, end;

int abs(int x){return x > 0 ? x : -x;}
int Max(int x, int y){return x > y ? x : y;}
int Min(int x, int y){return x < y ? x : y;}

bool cmp_x(const Point &a, const Point &b)
{
	if (a.x == b.x)
		return a.y < b.y;
	return a.x < b.x;
}

bool cmp_y(const Point &a, const Point &b)
{
	if (a.y == b.y)
		return a.x < b.x;
	return a.y < b.y;
}

void check_y()
{
	int i;
	int tmpstart, tmpend;
	sort(p, p + N, cmp_x);
	for (i = 0; i < N - 1; i++)
	{
		if (p[i].x != p[i + 1].x || abs(p[i].id - p[i + 1].id) == 1)
			continue;
		if (p[i + 1].y - p[i].y < mindis)
		{
			mindis = p[i + 1].y - p[i].y;
			start = Min(p[i].id, p[i + 1].id);
			end = Max(p[i].id, p[i + 1].id);
			mindir = p[i].id < p[i + 1].id ? 'N' : 'S';
		}
		else if (p[i + 1].y - p[i].y == mindis)
		{
			tmpstart = Min(p[i].id, p[i + 1].id);
			tmpend = Max(p[i].id, p[i + 1].id);
			if (tmpstart < start || (tmpstart == start && tmpend > end))
			{
				start = tmpstart;
				end = tmpend;
				mindir = p[i].id < p[i + 1].id ? 'N' : 'S';
			}
		}
	}
}

void check_x()
{
	int i;
	int tmpstart, tmpend, tmpmindis;
	sort(p, p + N, cmp_y);
	//按Y排序 
	for (i = 0; i < N - 1; i++)
	{
		if (p[i].y != p[i + 1].y || abs(p[i].id - p[i + 1].id) == 1)//如果是相邻点或者Y不同 
			continue;
		if (p[i + 1].x - p[i].x < mindis)
		{
			mindis = p[i + 1].x - p[i].x;
			start = Min(p[i].id, p[i + 1].id);
			end = Max(p[i].id, p[i + 1].id);
			mindir = p[i].id < p[i + 1].id ? 'E' : 'W';
		}
		else if (p[i + 1].x - p[i].x == mindis)
		{
			tmpstart = Min(p[i].id, p[i + 1].id);
			tmpend = Max(p[i].id, p[i + 1].id);
			if (tmpstart < start || (tmpstart == start && tmpend > end))
			{
				start = tmpstart;
				end = tmpend;
				mindir = p[i].id < p[i + 1].id ? 'E' : 'W';
			}
		}
	}
}

void Solve()
{
	int i;
	p[0].x = 0;
	p[0].y = 0;
	for (i = 0; i < N; i++)
	{
		if (s[i] == 'N')
		{
			p[i + 1].x = p[i].x;
			p[i + 1].y = p[i].y + 1;
		}
		else if (s[i] == 'S')
		{
			p[i + 1].x = p[i].x;
			p[i + 1].y = p[i].y - 1;
		}
		else if (s[i] == 'E')
		{
			p[i + 1].x = p[i].x + 1;
			p[i + 1].y = p[i].y;
		}
		else
		{
			p[i + 1].x = p[i].x - 1;
			p[i + 1].y = p[i].y;
		}
		p[i].id = i;
	}
	p[N].id = N;
	N++;
	mindis = N + 10;
	mindir = 0;
	start = N + 10;
	end = -10;
	check_y();
	check_x();
	printf("%d %d %d %c\n", mindis, start, end, mindir);
}

int main()
{
	while (EOF != scanf("%d", &N) && N)
	{
		getchar();
		gets(s);
		Solve();
	}
	return 0;
}