比赛 |
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