Submission #1519064

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1e9;

int solve(int M, map<int, vector<int>>& beam) {
    vector<int> res(M);
    for(auto& p : beam) {
        auto& b = p.second;
        sort(b.begin(), b.end());
        for(auto x : b) {
            if(x + 1 < M) {
                res[x + 1] = min(res[x + 1], res[x] + 1);
            }
        }
        for(int i = (int)b.size() - 1; i >= 0; --i) {
            if(b[i] - 1 >= 0) {
                res[b[i] - 1] = min(res[b[i] - 1], res[b[i]] + 1);
            }
        }
        for(auto x : b) {
            res[x] = INF;
        }
    }
    return *min_element(res.begin(), res.end());
}

int main() {
    int W, H, Q;
    cin >> W >> H >> Q;
    map<int, vector<int>> beam_y;
    map<int, vector<int>> beam_x;
    for(int i = 0; i < Q; ++i) {
        int t, d, x;
        cin >> t >> d >> x;
        if(d == 0) {
            beam_x[t].push_back(x - 1);
        } else {
            beam_y[t].push_back(x - 1);
        }
    }
    int yd = solve(H, beam_y);
    int xd = solve(W, beam_x);
    if(xd == INF || yd == INF) {
        cout << -1 << endl;
    } else {
        cout << yd + xd << endl;
    }
}

Submission Info

Judge Result