//============================================================================ // Name : 5c-but.cpp //============================================================================ #include <iostream> #include <deque> #include <map> #include <set> using namespace std; const int L = 3; set<long long> visitedKeys; long long capacity[L] = { 0, 0, 0 }; const int moves[][2] = { { 0, 1 }, { 0, 2 }, { 1, 0 }, { 1, 2 }, { 2, 0 }, { 2, 1 } }; const int MOVES_LENGTH = 6; long long* moveStateTo(long long *state, int mId) { long long *result = new long long[L + 1]; std::copy(state, state + L + 1, result); int from = moves[mId][0]; int to = moves[mId][1]; if (result[to] == capacity[to] || result[from] == 0) { return NULL; } long long emptySpace = capacity[to] - result[to]; long long volumeToMove = min(emptySpace, result[from]); result[to] += volumeToMove; result[from] -= volumeToMove; result[L]++; return result; } long long key(long long *state) { return state[0] | state[1] << 16 | state[2] << 32; } int main() { ios_base::sync_with_stdio(false); long long *volume = new long long[L + 1]; long long tmp; for (int i = 0; i < L; i++) { cin >> tmp; capacity[i] = tmp; } for (int i = 0; i < L; i++) { cin >> volume[i]; } volume[L] = 0; map<long long, long long> resultMap; const long long S = capacity[2] + 1; long long maxCapacity = volume[0] + volume[1] + volume[2]; for (long long i = maxCapacity + 1; i < S; i++) { resultMap[i] = -1L; } long long minCapacity = maxCapacity - capacity[1] - capacity[2]; for (long long i = 0L; i < minCapacity; i++) { resultMap[i] = -1L; } deque<long long*> queue; queue.push_back(volume); // long long state[L + 1], newState[L + 1]; long long *state, *newState; long long kv; while (resultMap.size() < S && !queue.empty()) { state = queue.front(); queue.pop_front(); for (int i = 0; i < L; i++) { if (!(resultMap.count(state[i]) > 0)) { resultMap[state[i]] = state[L]; } } for (int i = 0; i < MOVES_LENGTH; i++) { newState = moveStateTo(state, i); if (newState != NULL) { kv = key(newState); if (!(visitedKeys.count(kv) > 0)) { visitedKeys.insert(kv); queue.push_back(newState); } } } } for (long long i = 0; i < S; i++) { if (resultMap.count(i) > 0) { cout << resultMap[i] << " "; } else { cout << "-1 "; } } cout << 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 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 | //============================================================================ // Name : 5c-but.cpp //============================================================================ #include <iostream> #include <deque> #include <map> #include <set> using namespace std; const int L = 3; set<long long> visitedKeys; long long capacity[L] = { 0, 0, 0 }; const int moves[][2] = { { 0, 1 }, { 0, 2 }, { 1, 0 }, { 1, 2 }, { 2, 0 }, { 2, 1 } }; const int MOVES_LENGTH = 6; long long* moveStateTo(long long *state, int mId) { long long *result = new long long[L + 1]; std::copy(state, state + L + 1, result); int from = moves[mId][0]; int to = moves[mId][1]; if (result[to] == capacity[to] || result[from] == 0) { return NULL; } long long emptySpace = capacity[to] - result[to]; long long volumeToMove = min(emptySpace, result[from]); result[to] += volumeToMove; result[from] -= volumeToMove; result[L]++; return result; } long long key(long long *state) { return state[0] | state[1] << 16 | state[2] << 32; } int main() { ios_base::sync_with_stdio(false); long long *volume = new long long[L + 1]; long long tmp; for (int i = 0; i < L; i++) { cin >> tmp; capacity[i] = tmp; } for (int i = 0; i < L; i++) { cin >> volume[i]; } volume[L] = 0; map<long long, long long> resultMap; const long long S = capacity[2] + 1; long long maxCapacity = volume[0] + volume[1] + volume[2]; for (long long i = maxCapacity + 1; i < S; i++) { resultMap[i] = -1L; } long long minCapacity = maxCapacity - capacity[1] - capacity[2]; for (long long i = 0L; i < minCapacity; i++) { resultMap[i] = -1L; } deque<long long*> queue; queue.push_back(volume); // long long state[L + 1], newState[L + 1]; long long *state, *newState; long long kv; while (resultMap.size() < S && !queue.empty()) { state = queue.front(); queue.pop_front(); for (int i = 0; i < L; i++) { if (!(resultMap.count(state[i]) > 0)) { resultMap[state[i]] = state[L]; } } for (int i = 0; i < MOVES_LENGTH; i++) { newState = moveStateTo(state, i); if (newState != NULL) { kv = key(newState); if (!(visitedKeys.count(kv) > 0)) { visitedKeys.insert(kv); queue.push_back(newState); } } } } for (long long i = 0; i < S; i++) { if (resultMap.count(i) > 0) { cout << resultMap[i] << " "; } else { cout << "-1 "; } } cout << endl; return 0; } |