3 parts// Jug.h & Jug.cpp & main.cpp

In the movie Die Hard 3, Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. The solution they reached was to fill the 5-gallon jug, pour the 5- gallon jug into the 3-gallon jug (this left 2 gallons in the 5-gallon jug), empty the 3-gallon jug, pour the 5-gallon jug into the 3-gallon jug, fill the 5-gallon jug and then fill the 3-gallon jug from the 5-gallon jug, empty the 3 gallon jug, leaving 4 gallons in the 5 gallon jug Your assignment will be to generalize this problem in the follow manner You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use, each with a cost 1. you can fill jug A or B 2. you can empty jug A or B 3. you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A. problem is given by (Ca, Cb, N, CfA, cfB, ceA, , , coBA), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. cfA is the cost to fill A, cfB is the cost to fill B, ceA, is the cost to empty A, ceB is the cost to empty B, cpAB is the cost to pour A to B and cpBA is the cost to pour B to A. A solution is a sequence of steps that leaves jug A empty, and exactly N gallons in jug B. The possible steps are e empty A empty B pour A B pour B A success X fill means to fill the jug from the infinite water supply empty means to discard the water in the jug pour A B" means "pour the contents of jug A into jug B" success X' means that the goal has been accomplished, jug B contains N gallons at a cost of X Program Specs You MUST solve this problem by building and traversing a graph, if you find a cute math formula to solve the problem NO credit will be iven Write a Jug class that takes 9 parameters in the constructor. (Ca, Cb, N, CfA, CfB, , , , cp BA) Note: the order IS important. Also checking for valid input is something you should do. Your Jug class must have a solve0 member which will solve and then store the steps for the CHEAPEST solution in a string class Jugi public: Jug (int,int,int,int,int,int,int,int, int) ; Jug ) //solve is used to check input and find the solution if one exists //returns -1 if invalid inputs.solution set to empty string. //returns 0 if inputs are valid but a solution does not exist. solution set to empty string //returns 1 if solution is found and stores solution steps in solution string. int solve (string &solution); private: //anything else you need You may also find that you need an few helping structures to aid in the building of your graph. You may use queues, stacks, heaps, priority queues, trees or any other NON GRAPH structure you need. You make take these from old homework, or the STL. Also you MUST state in your comments at the top of the Jug.h file that you are using them and give credit where credit is due. Input input to your program consists of 9 ints defining one puzzle. Ca, Cb, N, CfA, cfB, , , cpBA. Ca and Cb are the capacities of jugs A and B, and N is the goal. the rest are the costs for each action. You will want to verify the costs are positive and 0