#include <iostream> #include <queue> #include <utility> int A,B,C; int a,b,c; const int N = 100005; int T[N]; bool va[N], vb[N], vc[N]; void input() { std::cin >> A >> B >> C >> a >> b >> c; for (int i = 0; i <= C; i++) { T[i] = -1; va[i] = false; vb[i] = false; vc[i] = false; } } struct state { int a,b,c,t; }; std::queue<state> Q; std::pair<int, int> move(int a, int b, int B) { int b2 = b + a; int a2 = 0; if (b2 > B) { a2 = b2 - B; b2 = B; } // std::cout << "move from " << a << " to " << b << " size " << B << " result " << a2 << " " << b2 << "\n"; return { a2, b2 }; } void solve() { Q.push({a,b,c,0}); while (!Q.empty()) { state s = Q.front(); // std::cout << s.a << " " << s.b << " " << s.c << " " << s.t << "\n"; Q.pop(); bool new_state = false; if (!va[s.a]) { T[s.a] = T[s.a] < 0 ? s.t : T[s.a]; new_state = true; va[s.a] = true; } if (!vb[s.b]) { T[s.b] = T[s.b] < 0 ? s.t : T[s.b]; new_state = true; vb[s.b] = true; } if (!vc[s.c]) { T[s.c] = T[s.c] < 0 ? s.t : T[s.c]; new_state = true; vc[s.c] = true; } if (new_state) { auto m1 = move(s.a, s.b, B); Q.push({m1.first, m1.second, s.c, s.t + 1}); auto m2 = move(s.a, s.c, C); Q.push({m2.first, s.b, m2.second, s.t + 1}); auto m3 = move(s.b, s.a, A); Q.push({m3.second, m3.first, s.c, s.t + 1}); auto m4 = move(s.b, s.c, C); Q.push({s.a, m4.first, m4.second, s.t + 1}); auto m5 = move(s.c, s.a, A); Q.push({m5.second, s.b, m5.first, s.t + 1}); auto m6 = move(s.c, s.b, B); Q.push({s.a, m6.second, m6.first, s.t + 1}); } } for (int i = 0; i <= C; i++) { std::cout << T[i] << " "; } std::cout << "\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); input(); solve(); 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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include <iostream> #include <queue> #include <utility> int A,B,C; int a,b,c; const int N = 100005; int T[N]; bool va[N], vb[N], vc[N]; void input() { std::cin >> A >> B >> C >> a >> b >> c; for (int i = 0; i <= C; i++) { T[i] = -1; va[i] = false; vb[i] = false; vc[i] = false; } } struct state { int a,b,c,t; }; std::queue<state> Q; std::pair<int, int> move(int a, int b, int B) { int b2 = b + a; int a2 = 0; if (b2 > B) { a2 = b2 - B; b2 = B; } // std::cout << "move from " << a << " to " << b << " size " << B << " result " << a2 << " " << b2 << "\n"; return { a2, b2 }; } void solve() { Q.push({a,b,c,0}); while (!Q.empty()) { state s = Q.front(); // std::cout << s.a << " " << s.b << " " << s.c << " " << s.t << "\n"; Q.pop(); bool new_state = false; if (!va[s.a]) { T[s.a] = T[s.a] < 0 ? s.t : T[s.a]; new_state = true; va[s.a] = true; } if (!vb[s.b]) { T[s.b] = T[s.b] < 0 ? s.t : T[s.b]; new_state = true; vb[s.b] = true; } if (!vc[s.c]) { T[s.c] = T[s.c] < 0 ? s.t : T[s.c]; new_state = true; vc[s.c] = true; } if (new_state) { auto m1 = move(s.a, s.b, B); Q.push({m1.first, m1.second, s.c, s.t + 1}); auto m2 = move(s.a, s.c, C); Q.push({m2.first, s.b, m2.second, s.t + 1}); auto m3 = move(s.b, s.a, A); Q.push({m3.second, m3.first, s.c, s.t + 1}); auto m4 = move(s.b, s.c, C); Q.push({s.a, m4.first, m4.second, s.t + 1}); auto m5 = move(s.c, s.a, A); Q.push({m5.second, s.b, m5.first, s.t + 1}); auto m6 = move(s.c, s.b, B); Q.push({s.a, m6.second, m6.first, s.t + 1}); } } for (int i = 0; i <= C; i++) { std::cout << T[i] << " "; } std::cout << "\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); input(); solve(); return 0; } |