571 - Jugs

Difficulty : medium

Solution Description :

BFS Problem

Pouring rule:
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.

1. At first push to queue jugA=0, jugB=0 and command=""
2. Pop from queue
3. If jugB==N then print command and break
4. Find 6 adjacency of pop value of jugA and jugB
    a. If jugA<Ca then change jugA=Ca and command="fill A" and push to queue
    b. If jugB<Cb then change jugB=Cb and command="fill B" and push to queue
    c. If jugA>0 then change jugA=0 and command="empty A" and push to queue
    d. if jugB>0 then change jugB=0 and command="empty B" and push to queue
    e. if jugA>0 and jugB<Cb then change the value of jugA and jugB using the pouring rule and command="pour A B" and push to queue
    f. if jugA<Ca and jugB>0  then change the value of jugA and jugB using the pouring rule and command="pour B A" and push to queue
goto step 2