제출 #140774

#제출 시각아이디문제언어결과실행 시간메모리
140774khrbuddy03물통 (KOI17_bucket)C++14
100 / 100
651 ms24396 KiB
#include <bits/stdc++.h>

using namespace std;

map<pair<int, int>, bool> vis;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int X, Y, A, B; cin >> X >> Y >> A >> B;
    queue<pair<int, pair<int, int>>> q;
    q.push(make_pair(0, make_pair(0, 0)));
    vis[make_pair(0, 0)] = true;
    while (!q.empty()) {
        int dist = q.front().first;
        int a = q.front().second.first, b = q.front().second.second;
        // cout << dist << ' ' << a << ' ' << b << '\n';
        q.pop();
        if (a == A && b == B) {
            cout << dist << '\n';
            return 0;
        }
        pair<int, int> next[6] = {{a, Y}, {X, b}, {a - min(a, Y - b), b + min(a, Y - b)}, {a + min(b, X - a), b - min(b, X - a)}, {a, 0}, {0, b}};
        for (int i = 0; i < 6; i++) {
            if (vis[next[i]]) continue;
            q.push(make_pair(dist + 1, next[i]));
            vis[next[i]] = true;
        }
    }
    cout << "-1\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...