1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <bits/stdc++.h>
using namespace std;
int N, xL, yL, xB, yB;
unordered_map<int, vector<int>> xSame;
unordered_map<int, vector<int>> ySame;
set<pair<int, int>> v;
// 1: horizontal
// 0: vertical
const int ISX = 1, ISY = 0;
queue<array<int, 3>> pq;
int main() {
ifstream cin("lasers.in");
ofstream cout("lasers.out");
cin >> N >> xL >> yL >> xB >> yB;
// update xSame/ySame for laser
xSame[xL].push_back(yL);
ySame[yL].push_back(xL);
xSame[xB].push_back(yB);
ySame[yB].push_back(xB);
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
xSame[a].push_back(b);
ySame[b].push_back(a);
}
pq.push({0, ISX, xL});
pq.push({0, ISY, yL});
while (! pq.empty()) {
array<int, 3> node = pq.front();
pq.pop();
int isanX = node[1], coord = node[2], val = node[0];
if ((isanX && coord == xB) || (! isanX && coord == yB)) {
cout << val;
return 0;
}
v.insert({isanX, coord});
if (isanX) {
// it is an X
for (int y : xSame[coord]) {
if (! v.count({ISY,y})) {
pq.push({val + 1, ISY, y});
}
}
}
else {
// it is a Y
for (int x : ySame[coord]) {
if (! v.count({ISX,x})) {
pq.push({val + 1, ISX, x});
}
}
}
}
}
|