#include <cstdio> #include <vector> #include <tuple> #include <set> const int maxc=100000; int res[maxc+1]; int main() { int A, B, C, a, b, c; scanf("%d%d%d%d%d%d",&A,&B,&C,&a,&b,&c); for(int i=0;i<=C;i++) res[i]=-1; res[a]=res[b]=res[c]=0; std::set<std::tuple<int,int,int> > visited; visited.insert(std::make_tuple(a,b,c)); std::vector<std::tuple<int,int,int> > q; std::vector<int> d; q.push_back(std::make_tuple(a,b,c)); d.push_back(0); for(int i=0;i<q.size();i++) { auto u=q[i]; int d_u=d[i]; int new_a, new_b, new_c; if(std::get<0>(u) > 0 && std::get<1>(u) < B) { //0->1 if(std::get<0>(u) <= B-std::get<1>(u)) { new_a=0; new_b=std::get<1>(u)+std::get<0>(u); } else { new_a=std::get<0>(u)-(B-std::get<1>(u)); new_b=B; } new_c=std::get<2>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<0>(u) > 0 && std::get<2>(u) < C) { //0->2 if(std::get<0>(u) <= C-std::get<2>(u)) { new_a=0; new_c=std::get<2>(u)+std::get<0>(u); } else { new_a=std::get<0>(u)-(C-std::get<2>(u)); new_c=C; } new_b=std::get<1>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<1>(u) > 0 && std::get<0>(u) < A) { //1->0 if(std::get<1>(u) <= A-std::get<0>(u)) { new_b=0; new_a=std::get<0>(u)+std::get<1>(u); } else { new_b=std::get<1>(u)-(A-std::get<0>(u)); new_a=A; } new_c=std::get<2>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<1>(u) > 0 && std::get<2>(u) < C) { //1->2 if(std::get<1>(u) <= C-std::get<2>(u)) { new_b=0; new_c=std::get<2>(u)+std::get<1>(u); } else { new_b=std::get<1>(u)-(C-std::get<2>(u)); new_c=C; } new_a=std::get<0>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<2>(u) > 0 && std::get<0>(u) < A) { //2->0 if(std::get<2>(u) <= A-std::get<0>(u)) { new_c=0; new_a=std::get<0>(u)+std::get<2>(u); } else { new_c=std::get<2>(u)-(A-std::get<0>(u)); new_a=A; } new_b=std::get<1>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<2>(u) > 0 && std::get<1>(u) < B) { //2->1 if(std::get<2>(u) <= B-std::get<1>(u)) { new_c=0; new_b=std::get<1>(u)+std::get<2>(u); } else { new_c=std::get<2>(u)-(B-std::get<1>(u)); new_b=B; } new_a=std::get<0>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } } for(int i=0;i<=C;i++) printf("%d ",res[i]); 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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 | #include <cstdio> #include <vector> #include <tuple> #include <set> const int maxc=100000; int res[maxc+1]; int main() { int A, B, C, a, b, c; scanf("%d%d%d%d%d%d",&A,&B,&C,&a,&b,&c); for(int i=0;i<=C;i++) res[i]=-1; res[a]=res[b]=res[c]=0; std::set<std::tuple<int,int,int> > visited; visited.insert(std::make_tuple(a,b,c)); std::vector<std::tuple<int,int,int> > q; std::vector<int> d; q.push_back(std::make_tuple(a,b,c)); d.push_back(0); for(int i=0;i<q.size();i++) { auto u=q[i]; int d_u=d[i]; int new_a, new_b, new_c; if(std::get<0>(u) > 0 && std::get<1>(u) < B) { //0->1 if(std::get<0>(u) <= B-std::get<1>(u)) { new_a=0; new_b=std::get<1>(u)+std::get<0>(u); } else { new_a=std::get<0>(u)-(B-std::get<1>(u)); new_b=B; } new_c=std::get<2>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<0>(u) > 0 && std::get<2>(u) < C) { //0->2 if(std::get<0>(u) <= C-std::get<2>(u)) { new_a=0; new_c=std::get<2>(u)+std::get<0>(u); } else { new_a=std::get<0>(u)-(C-std::get<2>(u)); new_c=C; } new_b=std::get<1>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<1>(u) > 0 && std::get<0>(u) < A) { //1->0 if(std::get<1>(u) <= A-std::get<0>(u)) { new_b=0; new_a=std::get<0>(u)+std::get<1>(u); } else { new_b=std::get<1>(u)-(A-std::get<0>(u)); new_a=A; } new_c=std::get<2>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<1>(u) > 0 && std::get<2>(u) < C) { //1->2 if(std::get<1>(u) <= C-std::get<2>(u)) { new_b=0; new_c=std::get<2>(u)+std::get<1>(u); } else { new_b=std::get<1>(u)-(C-std::get<2>(u)); new_c=C; } new_a=std::get<0>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<2>(u) > 0 && std::get<0>(u) < A) { //2->0 if(std::get<2>(u) <= A-std::get<0>(u)) { new_c=0; new_a=std::get<0>(u)+std::get<2>(u); } else { new_c=std::get<2>(u)-(A-std::get<0>(u)); new_a=A; } new_b=std::get<1>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } if(std::get<2>(u) > 0 && std::get<1>(u) < B) { //2->1 if(std::get<2>(u) <= B-std::get<1>(u)) { new_c=0; new_b=std::get<1>(u)+std::get<2>(u); } else { new_c=std::get<2>(u)-(B-std::get<1>(u)); new_b=B; } new_a=std::get<0>(u); auto v=std::make_tuple(new_a, new_b, new_c); if(visited.count(v) == 0) { visited.insert(v); if(res[new_a]==-1) res[new_a]=d_u+1; if(res[new_b]==-1) res[new_b]=d_u+1; if(res[new_c]==-1) res[new_c]=d_u+1; q.push_back(v); d.push_back(d_u+1); } } } for(int i=0;i<=C;i++) printf("%d ",res[i]); return 0; } |