比赛 20161223 评测结果 AAAATTTTTTA
题目名称 激光 最终得分 45
用户昵称 KZNS 运行时间 6.002 s
代码语言 C++ 内存使用 0.34 MiB
提交时间 2016-12-23 21:22:34
显示代码纯文本
//KZNS
#include <cstdio>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define Nmax 1003
typedef pair<int, int> pr;
pr x[Nmax];
pr y[Nmax];
int tx[Nmax];
int ty[Nmax];
int N, S[2], T[2];
void init() {
	scanf("%d %d %d %d %d", &N, &S[0], &S[1], &T[0], &T[1]);
	int a, b;
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &a, &b);
		x[i] = make_pair(a, i);
		y[i] = make_pair(b, i);
	}
	x[0] = make_pair(S[0], 0);
	y[0] = make_pair(S[1], 0);
	x[N+1] = make_pair(T[0], N+1);
	y[N+1] = make_pair(T[1], N+1);
	sort(x, x+1+N+1);
	sort(y, y+1+N+1);
	for (int i = 0; i <= N; i++) {
		tx[x[i].second] = i;
		ty[y[i].second] = i;
	}
}
bool ud[Nmax][2];
int v[Nmax][2];
void work() {
	queue<pr> ls;
	for (int i = 0; i < 2; i++) {
		ls.push(make_pair(0, i));
		ud[0][i] = true;
		v[0][i] = -1;
	}
	pr u;
	pr *ar;
	int id, dd;
	int a, b;
	while (!ls.empty()) {
		u = ls.front();
		ls.pop();
		if (u.second) {
			ar = y;
			id = ty[u.first];
		}
		else {
			ar = x;
			id = tx[u.first];
		}
		dd = ar[id].first;
		b = u.second^1;
		for (int i = id+1; i <= N+1 && ar[i].first == dd; i++) {
			a = ar[i].second;
			if (!ud[a][b]) {
				ud[a][b] = true;
				v[a][b] = v[u.first][u.second] + 1;
				if (a == N+1)
					goto ed;
				ls.push(make_pair(a, b));
			}
		}
		for (int i = id-1; i >= 0 && ar[i].first == dd; i--) {
			a = ar[i].second;
			if (!ud[a][b]) {
				ud[a][b] = true;
				v[a][b] = v[u.first][u.second] + 1;
				if (a == N+1)
					goto ed;
				ls.push(make_pair(a, b));
			}
		}
	}
	ed:
	int ans = -1;
	if (ud[N+1][0])
		ans = v[N+1][0];
	else if (ud[N+1][1])
		ans = v[N+1][1];
	printf("%d\n", ans);
}
int main() {
	freopen("lasers.in", "r", stdin);
	freopen("lasers.out", "w", stdout);
	init();
	if (S[0] == T[0] && S[1] == T[1])
		printf("0\n");
	else
		work();
	return 0;
}
//UBWH