#include <iostream> #include <queue> #include <array> #include <cstdint> #include <set> #include <vector> using namespace std; class butelka { public: int pojemnosc; int zawartosc; butelka (int poj): pojemnosc(poj){} butelka (const butelka& orig):pojemnosc(orig.pojemnosc), zawartosc(orig.zawartosc){} void operator=(const butelka& other) {pojemnosc=other.pojemnosc; zawartosc=other.zawartosc;} bool operator==(const butelka & other){return pojemnosc==other.pojemnosc && zawartosc==other.zawartosc;} bool empty(){return zawartosc==0;} bool full(){return zawartosc==pojemnosc;} int dolej(int ile) // zwraca ile sie nie zmiescilo { if (zawartosc+ile <=pojemnosc) { zawartosc+=ile; return 0; } else { int ileZostanie = ile-(pojemnosc-zawartosc); zawartosc = pojemnosc; return ileZostanie; } } friend void przelej(butelka& b1, butelka& b2) // przelej z b1 do b2 { int ileZostalo = b2.dolej(b1.zawartosc); b1.zawartosc = ileZostalo; } }; array<int,3> stan(const array<butelka, 3>& butelki) { array<int,3> stan={butelki[0].zawartosc, butelki[1].zawartosc, butelki[2].zawartosc}; return stan; } int main() { int a,b,c,x; cin>>a>>b>>c; array<butelka, 3> butelki0={butelka(a),butelka(b),butelka(c)}; for (uint32_t ii=0; ii<butelki0.size(); ii++) { cin>>x; butelki0[ii].dolej(x); } vector<int32_t> wyniki(butelki0.back().pojemnosc+1, -1); set<array<int,3>> odwiedzone; odwiedzone.insert(stan(butelki0)); queue<array<butelka, 3>> kolejka1, kolejka2; kolejka1.push(butelki0); uint32_t krok=0; while (!kolejka1.empty()) { while (!kolejka1.empty()) { array<butelka, 3> butelki = kolejka1.front(); for(auto it = butelki.begin(); it!=butelki.end(); ++it) if(wyniki[it->zawartosc]==-1) // nie bylo osiagniete wczesniej wyniki[it->zawartosc] = krok; for (auto it1 = butelki.begin(); it1!=butelki.end(); ++it1) for(auto it2 = butelki.begin(); it2!=butelki.end(); ++it2) if(it1 !=it2) if(!(it1->empty() || it2->full())) { przelej(*it1, *it2); if (odwiedzone.count(stan(butelki))==0) { odwiedzone.insert(stan(butelki)); kolejka2.push(butelki); } butelki = kolejka1.front(); } kolejka1.pop(); } krok++; swap(kolejka1, kolejka2); } for (uint32_t ii=0; ii<wyniki.size(); ii++) cout<<wyniki[ii]<<' '; 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 102 103 104 | #include <iostream> #include <queue> #include <array> #include <cstdint> #include <set> #include <vector> using namespace std; class butelka { public: int pojemnosc; int zawartosc; butelka (int poj): pojemnosc(poj){} butelka (const butelka& orig):pojemnosc(orig.pojemnosc), zawartosc(orig.zawartosc){} void operator=(const butelka& other) {pojemnosc=other.pojemnosc; zawartosc=other.zawartosc;} bool operator==(const butelka & other){return pojemnosc==other.pojemnosc && zawartosc==other.zawartosc;} bool empty(){return zawartosc==0;} bool full(){return zawartosc==pojemnosc;} int dolej(int ile) // zwraca ile sie nie zmiescilo { if (zawartosc+ile <=pojemnosc) { zawartosc+=ile; return 0; } else { int ileZostanie = ile-(pojemnosc-zawartosc); zawartosc = pojemnosc; return ileZostanie; } } friend void przelej(butelka& b1, butelka& b2) // przelej z b1 do b2 { int ileZostalo = b2.dolej(b1.zawartosc); b1.zawartosc = ileZostalo; } }; array<int,3> stan(const array<butelka, 3>& butelki) { array<int,3> stan={butelki[0].zawartosc, butelki[1].zawartosc, butelki[2].zawartosc}; return stan; } int main() { int a,b,c,x; cin>>a>>b>>c; array<butelka, 3> butelki0={butelka(a),butelka(b),butelka(c)}; for (uint32_t ii=0; ii<butelki0.size(); ii++) { cin>>x; butelki0[ii].dolej(x); } vector<int32_t> wyniki(butelki0.back().pojemnosc+1, -1); set<array<int,3>> odwiedzone; odwiedzone.insert(stan(butelki0)); queue<array<butelka, 3>> kolejka1, kolejka2; kolejka1.push(butelki0); uint32_t krok=0; while (!kolejka1.empty()) { while (!kolejka1.empty()) { array<butelka, 3> butelki = kolejka1.front(); for(auto it = butelki.begin(); it!=butelki.end(); ++it) if(wyniki[it->zawartosc]==-1) // nie bylo osiagniete wczesniej wyniki[it->zawartosc] = krok; for (auto it1 = butelki.begin(); it1!=butelki.end(); ++it1) for(auto it2 = butelki.begin(); it2!=butelki.end(); ++it2) if(it1 !=it2) if(!(it1->empty() || it2->full())) { przelej(*it1, *it2); if (odwiedzone.count(stan(butelki))==0) { odwiedzone.insert(stan(butelki)); kolejka2.push(butelki); } butelki = kolejka1.front(); } kolejka1.pop(); } krok++; swap(kolejka1, kolejka2); } for (uint32_t ii=0; ii<wyniki.size(); ii++) cout<<wyniki[ii]<<' '; cout<<endl; return 0; } |