#include <iostream> #include <unordered_map> #include <queue> using namespace std; int A,B,C,starta,startb,startc; struct state{ int a,b,c; long long hash() { return (long long)a*(B+1)+b; } friend ostream& operator<<(ostream& stream, const state& s) { stream << "(" << s.a << "," << s.b << "," << s.c << ")"; return stream; } }; unordered_map<long long,bool> visited; queue< pair<state,int> > q; int out[100009]; int main() { cin >> A >> B >> C; cin >> starta >> startb >> startc; for(int i=0; i<=C; i++) { out[i] = -1; } state start = {starta,startb,startc}; q.push({start,0}); visited[start.hash()] = true; while(!q.empty()) { state curr = q.front().first; // cout << curr << endl; int dist = q.front().second; q.pop(); if(out[curr.a] == -1) out[curr.a] = dist; if(out[curr.b] == -1) out[curr.b] = dist; if(out[curr.c] == -1) out[curr.c] = dist; // all possibilites int to_pour; state new_state; // a to b to_pour = min(curr.a,B-curr.b); if(to_pour != 0) { new_state = {curr.a-to_pour, curr.b+to_pour, curr.c}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // a to c to_pour = min(curr.a,C-curr.c); if(to_pour != 0) { new_state = {curr.a-to_pour, curr.b, curr.c+to_pour}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // b to a to_pour = min(curr.b,A-curr.a); if(to_pour != 0) { new_state = {curr.a+to_pour, curr.b-to_pour, curr.c}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // b to c to_pour = min(curr.b,C-curr.c); if(to_pour != 0) { new_state = {curr.a, curr.b-to_pour, curr.c+to_pour}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // c to a to_pour = min(curr.c,A-curr.a); if(to_pour != 0) { new_state = {curr.a+to_pour, curr.b, curr.c-to_pour}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // c to b to_pour = min(curr.c, B-curr.b); if(to_pour != 0) { new_state = {curr.a, curr.b+to_pour, curr.c-to_pour}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } } for(int i=0; i<=C; i++) { cout << out[i] << " "; } }
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 | #include <iostream> #include <unordered_map> #include <queue> using namespace std; int A,B,C,starta,startb,startc; struct state{ int a,b,c; long long hash() { return (long long)a*(B+1)+b; } friend ostream& operator<<(ostream& stream, const state& s) { stream << "(" << s.a << "," << s.b << "," << s.c << ")"; return stream; } }; unordered_map<long long,bool> visited; queue< pair<state,int> > q; int out[100009]; int main() { cin >> A >> B >> C; cin >> starta >> startb >> startc; for(int i=0; i<=C; i++) { out[i] = -1; } state start = {starta,startb,startc}; q.push({start,0}); visited[start.hash()] = true; while(!q.empty()) { state curr = q.front().first; // cout << curr << endl; int dist = q.front().second; q.pop(); if(out[curr.a] == -1) out[curr.a] = dist; if(out[curr.b] == -1) out[curr.b] = dist; if(out[curr.c] == -1) out[curr.c] = dist; // all possibilites int to_pour; state new_state; // a to b to_pour = min(curr.a,B-curr.b); if(to_pour != 0) { new_state = {curr.a-to_pour, curr.b+to_pour, curr.c}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // a to c to_pour = min(curr.a,C-curr.c); if(to_pour != 0) { new_state = {curr.a-to_pour, curr.b, curr.c+to_pour}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // b to a to_pour = min(curr.b,A-curr.a); if(to_pour != 0) { new_state = {curr.a+to_pour, curr.b-to_pour, curr.c}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // b to c to_pour = min(curr.b,C-curr.c); if(to_pour != 0) { new_state = {curr.a, curr.b-to_pour, curr.c+to_pour}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // c to a to_pour = min(curr.c,A-curr.a); if(to_pour != 0) { new_state = {curr.a+to_pour, curr.b, curr.c-to_pour}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } // c to b to_pour = min(curr.c, B-curr.b); if(to_pour != 0) { new_state = {curr.a, curr.b+to_pour, curr.c-to_pour}; // cout << new_state << " is " << visited[new_state.hash()] << endl; if(!visited[new_state.hash()]) { q.push({new_state, dist+1}); visited[new_state.hash()] = true; } } } for(int i=0; i<=C; i++) { cout << out[i] << " "; } } |