1394.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1394 on 2006-01-19 at 00:45:57 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 256000;

class Point {
public:
	int x, y, o;
	void make(int, int, int);
	bool operator <(const Point&) const;
};
void Point::make(int cx = 0, int cy = 0, int co = -1) {
	x = cx; y = cy; o = co;
}
bool Point::operator <(const Point& p) const {
	if(x != p.x) return x < p.x;
	else return y < p.y;
}

class List {
private:
	Point point[MAX];
	int n;
public:
	int minl, minb, mine;
	char mind;
	void make();
	void insert(int, int);
	void find(char, char);
	void change();
};
void List::make() {
	point[0].make(0, 0, 0); n = 1;
	minl = minb = MAX; mine = 0;
}
void List::insert(int x, int y) {
	point[n].make(x, y, n); n++;
}
void List::find(char up, char down) {
	sort(point, point+n);
	int prevx = -MAX, i;
	for(i = 0; i < n; i++) {
		if(prevx != point[i].x) prevx = point[i].x;
		else if(abs(point[i].o-point[i-1].o) != 1) {
			int src = min(point[i-1].o, point[i].o);
			int dis = max(point[i-1].o, point[i].o);
			if((minl > point[i].y-point[i-1].y)
				|| (minl == point[i].y-point[i-1].y && minb > src)
				|| (minl == point[i].y-point[i-1].y && minb == src && mine < dis)) {
				minl = point[i].y - point[i-1].y;
				minb = src;
				mine = dis;
				if(src == point[i-1].o) mind = up;
				else mind = down;
			}
		}
	}
}
void List::change() {
	int i;
	for(i = 0; i < n; i++) swap(point[i].x, point[i].y);
}

List list;

int main()
{
	Point now;
	char dir[MAX];
	int n, i, t, T;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d\n", &n);
		list.make(); now.make();
		gets(dir);
		for(i = 0; i < n; i++) {
			switch(dir[i]) {
			case 'N': now.y++; break;
			case 'S': now.y--; break;
			case 'W': now.x--; break;
			case 'E': now.x++; break;
			}
			list.insert(now.x, now.y);
		}
		list.find('N', 'S');
		list.change();
		list.find('E', 'W');
		printf("%d %d %d %c\n", list.minl, list.minb, list.mine, list.mind);
	}

	return 0;
}