C - Programming Guide

#include<iostream.h>
#include<conio.h>
#include<stdio.h>

class Queue
{
            public:
                        Queue()
                        : head(NULL), tail(NULL)
                        {
                        }
                        void enqueue(int i)
                        {
                            if (head == NULL)
                                head = tail = new Node(i, NULL);
                            else
                                tail = tail->next = new Node(i, NULL);
                        }
                        int dequeue()
                        {
                                    Node* old = head;
                                    head = head->next;
                                    int i = old->i;
                                    delete old;
                                    return i;
                        }
                        int isEmpty()
                        {
                                    return (head == NULL);
                        }
                        ~Queue()
                        {
                                    while (!isEmpty())
                                    dequeue();
                        }
            private:
                        struct Node
                        {
                                    int i;
                                    Node* next;

                                    Node(int iP, Node* nextP)
                                    : i(iP), next(nextP)
                                    {
                                    }
                        } *head, *tail;
} iQueue;

const int MAX = 100;
const int MAX_I = (MAX + 1) * (MAX + 1);

int N, M, k, n, m;

int distance[MAX_I];
int prev[MAX_I];

int nmToI(int n, int m)
{
            return n * (M + 1) + m;
}

int iToN(int i)
{
            return i / (M + 1);
}

int iToM(int i)
{
            return i % (M + 1);
}

void trace(int i)
{
            if (i > 0)
                        trace(prev[i]);
            cout <<"    "<<iToN(i) << "   |   " <<iToM(i) << "\n";
}

void test(int n, int m, int n1, int m1)
{
            if (n1 < 0 || n1 > N || m1 < 0 || m1 > M)
                        return;

            int i1 = nmToI(n1, m1);

            if (distance[i1] != 0)
                        return;

            int i = nmToI(n, m);
            distance[i1] = distance[i] + 1;
            prev[i1] = i;
            iQueue.enqueue(i1);
}

int solve()
{
            n = m = 0;
            distance[0] = 1;
            iQueue.enqueue(0);

            while (!iQueue.isEmpty())
            {
                        int i = iQueue.dequeue();
                        int n = iToN(i);
                        int m = iToM(i);

                        if (n == k || m == k || n + m == k)
                        return i;

            // empty out a jug
                        test(n, m, 0, m);
                        test(n, m, n, 0);

            // fill a jug
                        test(n, m, N, m);
                        test(n, m, n, M);

            // pour one to another until source is empty
                        test(n, m, 0, n + m);
                        test(n, m, n + m, 0);

            // pour one to another until destination is full
                        test(n, m, n - M + m, M);
                        test(n, m, N, m - N + n);
            }
            return -1;
}

void main()
{
            clrscr();
            cout<<"Please enter the number of gallons in first jug:  ";
            cin>>N;
            cout<<"Please enter the number of gallons in second jug:  ";
            cin>>M;
            cout<<"Please enter the vol. of water to be left finally: ";
            cin>>k;

            int i = solve();

            cout<<"  JUG 1  "<<"  JUG 2 \n";
            cout<<"----------------\n";
            if (i == -1)
                        cout << 0 << "\n";
            else
            {
                        cout << distance[i] << "\n";
                        trace(i);
            }
            cout << -1 << "\n";
            getch();
}