POUR1 - Pouring water
Given two vessels, one of which can accommodate a litres of water and the other - b litres of water, determine the number of steps required to obtain exactly c litres of water in one of the vessels.
At the beginning both vessels are empty. The following operations are counted as 'steps':
- emptying a vessel,
- filling a vessel,
- pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.
An integer t, 1<=t<=100, denoting the number of testcases, followed by t sets of input data, each consisting of three positive integers a, b, c, not larger than 40000, given in separate lines.
For each set of input data, output the minimum number of steps required to obtain c litres, or -1 if this is impossible.
2 5 2 3 2 3 4
AC in BFS and unordered_maps to mark visited nodes/states
can anyone please give some corner test cases. As it is difficult to debug without it. I also tested so many cases but did not find the error!
You must simulate by doing "pouring action" only in one jug and "discharging action" only in the opposite jug.
Some optimisations necessary for while using BFS, otherwise TLE. Good question!
good question .
Good question to ponder. Finally AC using concept of Diophantine equation
Diophantine equation px+qy = r with a little bit simulation
Frankly,I don't know graphs.I could solve it perfectly with recursion.I wonder why graphs??