• Problem

  水罐问题，给你两个指定体积的水罐，要求得到目标体积的水量。

• Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <sstream>
using namespace std;
class Node {
public:
    Node(int i = 0, int j = 0) {
        set(i, j);
        s = toString();
        fn = -1;
        step = 0;
    }
    void set(int i, int j) {
        first = i;
        second = j;
    }
    void after(Node &from) {
        s = from.s + "->" + toString();
        step = from.step + 1;
    }
    void freshFn(int &final) {
        fn = step + min(abs(final - first), abs(final - second));
    }
    int first;
    int second;
    string s;
    int fn;
    int step;

    string toString() {
        std::stringstream out1;
        out1 << "(" << first << "," << second << ")";
        return out1.str();
    }
};

string Asearch(Node ini, Node cap, int final, int &counter) {
    vector<Node> q;
    Node cur, temp;
    string str = "not found";
    unordered_map<string, int> finded;
    auto add = [&](Node &t) {
        string s = t.toString();
        if (finded[s] && finded[s] <= t.step) {
            return;
        }
        t.after(cur);
        temp.freshFn(final);
        q.push_back(t);
    };

    q.push_back(ini);

    while (q.size()) {
        cur = q[0];
        q.erase(q.begin());
        finded[cur.toString()] = cur.step;
        counter++;

        if (cur.first == final) {
            str = cur.s;
            break;
        }

        temp = cur;

        // fill first jug;
        if (cur.first < cap.first) {
            temp.set(cap.first, cur.second);
            add(temp);
        }

        if (cur.second < cap.second) {
            temp.set(cur.first, cap.second);
            add(temp);
        }

        //Empty 1st Jug
        if (cur.first > 0) {
            temp.set(0, cur.second);
            add(temp);
        }
        //Empty 2nd Jug
        if (cur.second > 0) {
            temp.set(cur.first, 0);
            add(temp);
        }
        // Pour from 1st jug to 2nd jug
        if (cur.first && cur.second < cap.second) {
            int dis = min(cur.first, cap.second - cur.second);
            temp.set(cur.first - dis, cur.second + dis);
            if (dis) {
                add(temp);
            }

        }
        // Pour from 2nd jug to 1st jug
        if (cur.second && cur.first < cap.first) {
            int dis = min(cur.second, cap.first - cur.first);
            temp.set(cur.first + dis, cur.second - dis);
            if (dis) {
                add(temp);
            }
        }

        sort(q.begin(), q.end(), [&](const Node& a, const Node& b) {
            return a.fn < b.fn;
        });

    }

    return str;
}


int main()
{

    //Using BSF to find the answer
    while (true) {
        Node cap, ini;
        int final;

        //Input initial values
        cout << "Enter the capacity of 2 jugs\n";
        cin >> cap.first >> cap.second;
        //input final values
        cout << "Enter the required jug config\n";
        cin >> final;

        int counter = 0;
        cout << "result: " << Asearch(ini, cap, final, counter) << endl;
        cout << "check times: " << counter << endl << endl;
    }

    return 0;
}

• Result