#include <iostream> #include <stdio.h> using namespace std; int MAX_VOLUME = 100003; int BOTTLES = 3; int TRANSFERS = BOTTLES * (BOTTLES - 1); int EMPTY = 0; int FULL = 1; int smallest(int a, int b) { return a < b ? a : b; } struct State { int volume[3]; }; int next(int iBottle) { return (iBottle + 1) % BOTTLES; } int index(int extreme, int bottle, int volume) { return ((extreme * BOTTLES) + bottle) * MAX_VOLUME + volume; } int index(State state, State max) { for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { if (state.volume[iBottle] == 0) { return index(EMPTY, iBottle, state.volume[next(iBottle)]); } if (state.volume[iBottle] == max.volume[iBottle]) { return index(FULL, iBottle, state.volume[next(iBottle)]); } } return -1; } State transfer(State current, State max, int emptying, int filling) { int emptyingVolume = current.volume[emptying]; int fillingVolume = current.volume[filling]; int fillingMax = max.volume[filling]; int change = smallest(emptyingVolume, fillingMax - fillingVolume); State result; for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { result.volume[iBottle] = current.volume[iBottle]; } result.volume[emptying] -= change; result.volume[filling] += change; return result; } int main() { State max; for (int iiBottle = 0; iiBottle < BOTTLES; iiBottle++) { cin >> max.volume[iiBottle]; } State initial; for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { cin >> initial.volume[iBottle]; } int stepsToReach[2 * BOTTLES * MAX_VOLUME]; for (int i = 0; i < 2 * BOTTLES * MAX_VOLUME; i++) { stepsToReach[i] = -1; } int solution[MAX_VOLUME]; for (int i = 0; i < MAX_VOLUME; i++) { solution[i] = -1; } int initialIndex = index(initial, max); if (initialIndex >= 0) { stepsToReach[initialIndex] = 0; } for (int i = 0; i < BOTTLES; i++) { for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { int volume = initial.volume[iBottle]; solution[volume] = 0; } } State queue[2 * BOTTLES * MAX_VOLUME + 100]; queue[0] = initial; int queueStart = 0; int queueEnd = 1; while (queueEnd - queueStart > 0) { State state = queue[queueStart++]; int code = index(state, max); int steps = code < 0 ? 0 : stepsToReach[code]; for (int fromBottle = 0; fromBottle < BOTTLES; fromBottle++) { for (int toBottle = 0; toBottle < BOTTLES; toBottle++) { if (fromBottle != toBottle) { State nextState = transfer(state, max, fromBottle, toBottle); int transferIndex = index(nextState, max); if (stepsToReach[transferIndex] == -1) { stepsToReach[transferIndex] = steps + 1; queue[queueEnd++] = nextState; for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { int volume = nextState.volume[iBottle]; if (solution[volume] == -1 || steps + 1 < solution[volume]) { solution[volume] = steps + 1; } } } } } } } printf("%d", solution[0]); for (int i = 1; i <= max.volume[2]; i++) { printf(" %d", solution[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 | #include <iostream> #include <stdio.h> using namespace std; int MAX_VOLUME = 100003; int BOTTLES = 3; int TRANSFERS = BOTTLES * (BOTTLES - 1); int EMPTY = 0; int FULL = 1; int smallest(int a, int b) { return a < b ? a : b; } struct State { int volume[3]; }; int next(int iBottle) { return (iBottle + 1) % BOTTLES; } int index(int extreme, int bottle, int volume) { return ((extreme * BOTTLES) + bottle) * MAX_VOLUME + volume; } int index(State state, State max) { for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { if (state.volume[iBottle] == 0) { return index(EMPTY, iBottle, state.volume[next(iBottle)]); } if (state.volume[iBottle] == max.volume[iBottle]) { return index(FULL, iBottle, state.volume[next(iBottle)]); } } return -1; } State transfer(State current, State max, int emptying, int filling) { int emptyingVolume = current.volume[emptying]; int fillingVolume = current.volume[filling]; int fillingMax = max.volume[filling]; int change = smallest(emptyingVolume, fillingMax - fillingVolume); State result; for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { result.volume[iBottle] = current.volume[iBottle]; } result.volume[emptying] -= change; result.volume[filling] += change; return result; } int main() { State max; for (int iiBottle = 0; iiBottle < BOTTLES; iiBottle++) { cin >> max.volume[iiBottle]; } State initial; for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { cin >> initial.volume[iBottle]; } int stepsToReach[2 * BOTTLES * MAX_VOLUME]; for (int i = 0; i < 2 * BOTTLES * MAX_VOLUME; i++) { stepsToReach[i] = -1; } int solution[MAX_VOLUME]; for (int i = 0; i < MAX_VOLUME; i++) { solution[i] = -1; } int initialIndex = index(initial, max); if (initialIndex >= 0) { stepsToReach[initialIndex] = 0; } for (int i = 0; i < BOTTLES; i++) { for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { int volume = initial.volume[iBottle]; solution[volume] = 0; } } State queue[2 * BOTTLES * MAX_VOLUME + 100]; queue[0] = initial; int queueStart = 0; int queueEnd = 1; while (queueEnd - queueStart > 0) { State state = queue[queueStart++]; int code = index(state, max); int steps = code < 0 ? 0 : stepsToReach[code]; for (int fromBottle = 0; fromBottle < BOTTLES; fromBottle++) { for (int toBottle = 0; toBottle < BOTTLES; toBottle++) { if (fromBottle != toBottle) { State nextState = transfer(state, max, fromBottle, toBottle); int transferIndex = index(nextState, max); if (stepsToReach[transferIndex] == -1) { stepsToReach[transferIndex] = steps + 1; queue[queueEnd++] = nextState; for (int iBottle = 0; iBottle < BOTTLES; iBottle++) { int volume = nextState.volume[iBottle]; if (solution[volume] == -1 || steps + 1 < solution[volume]) { solution[volume] = steps + 1; } } } } } } } printf("%d", solution[0]); for (int i = 1; i <= max.volume[2]; i++) { printf(" %d", solution[i]); } return 0; } |