#include <iostream> #include <set> #include <array> #include <vector> #include <queue> bool contains(const std::array<int, 3> &value, const std::set<std::array<int, 3>> &cache) { return cache.find(value) != cache.end(); } typedef std::array<int, 3> Node; typedef std::pair<std::array<int, 3>, int> FifoEl; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::set<std::array<int, 3>> cache; int resultCount = 0; int aStart, bStart, cStart, a, b, c; std::cin >> a >> b >> c >> aStart >> bStart >> cStart; std::array<int, 3> sizes{a, b, c}; std::vector<int> result(c + 1, -1); std::queue<FifoEl> fifo; fifo.emplace(std::make_pair<Node, int>({aStart, bStart, cStart}, 0)); cache.insert({aStart, bStart, cStart}); bool stopped = false; while (!fifo.empty()) { const auto &element = fifo.front(); for (auto v: element.first) { if (result[v] == -1) { result[v] = element.second; if (++resultCount == c + 1) { stopped = true; break; } } } if (stopped) break; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i != j) { if (element.first[i] > 0 && element.first[j] < sizes[j]) { const Node &prevNode = element.first; Node n = prevNode; n[i] = std::max(0, prevNode[i] - (sizes[j] - prevNode[j])); n[j] = std::min(sizes[j], prevNode[j] + prevNode[i]); if (!contains(n, cache)) { cache.insert(n); fifo.push({n, element.second + 1}); } } } } } fifo.pop(); } for (auto i: result) { std::cout << i << " "; } std::cout << std::endl; return 0; }
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 70 71 72 73 74 | #include <iostream> #include <set> #include <array> #include <vector> #include <queue> bool contains(const std::array<int, 3> &value, const std::set<std::array<int, 3>> &cache) { return cache.find(value) != cache.end(); } typedef std::array<int, 3> Node; typedef std::pair<std::array<int, 3>, int> FifoEl; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::set<std::array<int, 3>> cache; int resultCount = 0; int aStart, bStart, cStart, a, b, c; std::cin >> a >> b >> c >> aStart >> bStart >> cStart; std::array<int, 3> sizes{a, b, c}; std::vector<int> result(c + 1, -1); std::queue<FifoEl> fifo; fifo.emplace(std::make_pair<Node, int>({aStart, bStart, cStart}, 0)); cache.insert({aStart, bStart, cStart}); bool stopped = false; while (!fifo.empty()) { const auto &element = fifo.front(); for (auto v: element.first) { if (result[v] == -1) { result[v] = element.second; if (++resultCount == c + 1) { stopped = true; break; } } } if (stopped) break; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i != j) { if (element.first[i] > 0 && element.first[j] < sizes[j]) { const Node &prevNode = element.first; Node n = prevNode; n[i] = std::max(0, prevNode[i] - (sizes[j] - prevNode[j])); n[j] = std::min(sizes[j], prevNode[j] + prevNode[i]); if (!contains(n, cache)) { cache.insert(n); fifo.push({n, element.second + 1}); } } } } } fifo.pop(); } for (auto i: result) { std::cout << i << " "; } std::cout << std::endl; return 0; } |