At Acme Utilities, you are given two water jugs with capacities jug1 and jug2, and a target amount target. Starting from both jugs empty, return a shortest sequence of valid operations that results in exactly target gallons in either jug.
Valid operations are:
Implement a function that takes three integers: jug1, jug2, and target.
Return a list of states, where each state is [a, b] representing the current amount of water in jug 1 and jug 2. The returned list must start with [0, 0] and end at a state where a == target or b == target. If no solution exists, return an empty list.
Example 1
Input: jug1 = 3, jug2 = 5, target = 4
Output: [[0,0],[0,5],[3,2],[0,2],[2,0],[2,5],[3,4]]
Explanation: The final state has 4 gallons in the 5-gallon jug.
Example 2
Input: jug1 = 2, jug2 = 6, target = 5
Output: []
Explanation: It is impossible to measure exactly 5 gallons with these jug sizes.
1 <= jug1, jug2 <= 1000 <= target <= max(jug1, jug2)