[第二轮] 3/25-3/31 CareerCup 6.3

You have a five-quart jug, a three-quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water? Note that the jugs are oddly shaped, such that filling up exactly "half" of the jug would be impossible.

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

To generalize this problem, you make the volumes of those two jugs variables. Then we can transform this problem into an implicit graph search problem. If we use BFS, then the answer we find requires the fewest steps. The following is the link to code. https://gist.github.com/ryancooper/12fe286dd4f640a29fe3
I write it in a rush, so it probably contains flaws, but for this particular case, it works just fine. And you can also get the general idea of what i say above.

I know. But isn't it funny to think of the generalized problem

https://gist.github.com/Jnight/5269223

#include <iostream>
#include <stack>

using namespace std;

#define JUG_A   5
#define JUG_B   3

struct node
{
        struct node * parent;
        struct node * childs;
        struct node * next;
        int a;  /* jug a */
        int b;  /* jug b */
        int c; /* total of summary */

        node (node* pNode)
        {
                a = pNode->a;
                b = pNode->b;
                c = pNode->c;
                parent = pNode;
                childs = NULL;
                next = NULL;
        }
        node ()
        {
                parent = NULL;
                childs = NULL;
                next = NULL;

                a = 0;
                b = 0;
                c = 0;
        }
        bool OK(int n) {
                if(a == n || b == n || c == n
                /*|| a+b == n || a + c == n || b + c == n*/)
                {
                        return true;
                }
                return false;
        }
};

void printNode(const node * pNode)
{
        cout << " " << pNode->a << " " << pNode->b << " " << pNode->c << endl;
}
node *fillNode(node* pNode )
{
        int t;
        node * tmp;
        /* fill up jug a */
        node* pFillJugA  = new node(pNode);
        pNode->childs = pFillJugA;
        tmp = pFillJugA;
        pFillJugA->a = JUG_A ;

        /* fill up jug b */
        node * pFillJugB = new node(pNode);
        tmp->next = pFillJugB;
        tmp = pFillJugB;
        pFillJugB->b = JUG_B;

        if(pNode->a > 0)
        {
                /* from jug a to b */
                node *pFromAToB = new node(pNode);
                tmp->next = pFromAToB ;
                tmp = pFromAToB;
                t = JUG_B - pFromAToB->b;
                pFromAToB->a -= t;
                pFromAToB->b += t;
        }
        if(pNode->b > 0)
        {
                /* from jug b to a */
                node * pFromB2A = new node(pNode);
                tmp->next = pFromB2A;
                tmp = pFromB2A;
                t = JUG_A - pFromB2A->a ;
                t = t > pFromB2A->b ? pFromB2A->b : t;
                pFromB2A->a += t;
                pFromB2A->b -= t;
        }
        if(pNode->a > 0)
        {
                /* from a to c */
                node * pFromA2C = new node(pNode);
                tmp->next = pFromA2C;
                tmp = pFromA2C;
                pFromA2C->c += pFromA2C->a;
                pFromA2C->a = 0;
        }
        if(pNode->b > 0)
        {
                /* from b to c */
                node * pFromB2C = new node(pNode);
                tmp->next = pFromB2C;
                tmp = pFromB2C;
                pFromB2C->c += pFromB2C->b;
                pFromB2C->b = 0;
        }
        return pFillJugA;
}
void destroyNode(stack<node *> &sn)
{
        node * first, *tmp;
        while(!sn.empty())
        {
                first = sn.top();
                sn.pop();
                while(first)
                {
                        tmp = first->next;
                        delete first;
                        first = tmp;
                }
        }
}
void search(int n)
{
        stack<node *> sNode;
        node * cur =  new node();
        sNode.push(cur);
        bool flag = false;
        node * first , * tmp;

        do
        {
                first = NULL;
                cur = sNode.top();
                while(cur)
                {
                        if(cur->OK(n)) {flag =true; break;}
                        node * retnode = fillNode(cur);
                        if(first == NULL) { first = retnode;}
                        else {
                                tmp = first;
                                while(tmp->next)
                                {
                                        tmp = tmp->next;
                                }
                                tmp->next = retnode;
                        }
                        cur = cur->next;
                }
                sNode.push(first);
        } while(!flag);
        stack<node*> outPutNode;
        while(cur)
        {
                outPutNode.push(cur);
                cur = cur->parent;
        }

        cout <<endl;
        while(!outPutNode.empty())
        {
                printNode(outPutNode.top());
                outPutNode.pop();
        }
        destroyNode(sNode);
}

int main()
{
        int n ;
        cout << endl<< "Please input the quart you want to get : " ;
        while(cin >> n)
        {
                if(n <= 0) { break;}
                search(n);
                cout << endl << "Please input the quart you want to get : " ;
        }

        return 0;
}

对于 n 大于 5 的情况，可以优化一下:
int tc = 0;
while(n >=5 )
                {
                        cout << " " << 5 << " " << 0 << " " << tc << endl;
                        tc += 5;
                        cout << " " << 0 << " " << 0 << " " << tc << endl;
                        n -=5;
                }
                if( n > 0) { search(n) ;}