Program Specs You MUST write this program by building and traversing a graph, if you find a cute math formula to solve the problem NO credit will be given. Create a [login to view URL] that explains your algorithm, think of it as a design spec. Someone reading it, that can code in any language, should be able to code your algorithm without having to ask you a bunch of questions. 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. for the complete detail please check the zip file, it contain the complete requirement for the program
## Deliverables
A problem is given by (Ca, Cb, N, cfA, cfB, ceA, ceB, cpAB, cpBA), 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 fill A fill B 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 where "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. Write a Jug class (located in jug.h / [login to view URL]) that takes 9 parameters in the constructor. (Ca, Cb, N, cfA, cfB, ceA, ceB, cpAB, cpBA) Note: the order IS important, Also checking for valid input is something you should do. Your Jug class must have a Solve() member which will solve and then print the CHEAPEST solution. class Jug { 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 invalid inputs. Do not print anything. //returns 0 if inputs are valid but a solution does not exist. Do not print anything. //returns 1 if solution is found and also prints solution. int Solve(); private: //anything else you need }; for the complete detail please check the zip file, it contain the complete requirement for the program
## Platform
program must run on c++ or linux