USACO 2016 Gold December P3. Lasers and Mirrors

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});
                }
            }
        }
    }

}