Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cctype>
- #include <climits>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <list>
- #include <map>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <string>
- #include <vector>
- #define inf 1000000000
- #define MAXN 100000
- #define swap(a,b) a^=b; b^=a; a^=b;
- using namespace std;
- struct state {
- vector<int> a;
- int nr_moves;
- state *previous;
- int i, j;
- state(int _nr_moves, vector<int> _a, int _i = 0, int _j = 0) {
- nr_moves = _nr_moves; a = _a; i = _i; j = _j;
- }
- };
- int maxes[100];
- int n;
- void print(state *s) {
- int br = 0;
- while (s != NULL && br++ < 3) {
- s = s->previous;
- printf("s.nr_moves:%d s->i:%d s->j:%d\n", s->nr_moves, s->i, s->j);
- }
- }
- int main() {
- scanf("%d", &n);
- for (int i = 0; i < n; ++i) {
- scanf("%d", &maxes[i]);
- }
- maxes[n] = INT_MAX;
- int where;
- scanf("%d", &where);
- for (int i = 0; i < n; ++i) {
- if (maxes[i] == where) {
- where = i;
- break;
- }
- }
- int cap;
- scanf("%d", &cap);
- vector<int> a = vector<int>(n, 0);
- a.push_back(inf);
- ++n;
- queue<state> kju;
- kju.push(state(0, a));
- set<string> bio;
- while (!kju.empty()) {
- state s = kju.front(); kju.pop();
- if (s.a[where] == cap) {
- print(&s);
- // printf("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\n");
- return 0;
- }
- string key = "";
- char st[10];
- for (int i = 0; i < n-1; ++i) {
- sprintf(st, "%5d#", s.a[i]);
- key += string(st);
- }
- printf("key:%s\n", key.c_str());
- if (bio.find(key) != bio.end()) continue;
- bio.insert(key);
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- if (i == j) continue;
- printf("i:%d j:%d\n", i, j);
- // from i to j
- if (s.a[i] != 0 && s.a[j] != maxes[j]) {
- printf("ubacujemo vodu!\n");
- int litres = min(s.a[i], maxes[j] - s.a[j]);
- a = s.a;
- a[i] -= litres;
- a[j] += litres;
- if (i < n-1) {
- sprintf(st, "%5d#", a[i]);
- key.replace(i*6, 6, string(st));
- }
- if (j < n-1) {
- sprintf(st, "%5d#", a[j]);
- key.replace(j*6, 6, string(st));
- }
- printf("key:%s\n", key.c_str());
- if (bio.find(key) == bio.end()) {
- state *new_state = new state(s.nr_moves+1, a, i, j);
- new_state->previous = &s;
- kju.push(*new_state);
- }
- if (i < n-1) {
- sprintf(st, "%5d#", s.a[i]);
- key.replace(i*6, 6, string(st));
- }
- if (j < n-1) {
- sprintf(st, "%5d#", s.a[j]);
- key.replace(j*6, 6, string(st));
- }
- printf("key:%s\n", key.c_str());
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement