399. Water Jug Problem Using BFS

You have two jugs with capacities a and b liters and an unlimited water supply. In one move you may fully fill either jug, fully empty either jug, or pour one jug into the other until either the source is empty or the destination is full. Starting from both jugs empty, find the minimum number of moves needed to have exactly 'target' liters in either jug. Print -1 if it's impossible.

Input: The first line contains a, the second line contains b, and the third line contains target - the two jug capacities and the target amount. Output: Print a single integer - the minimum number of moves to measure exactly target liters, or -1 if impossible.

1 <= a, b <= 1000, 0 <= target <= max(a, b)

This is a great example of recognizing an IMPLICIT graph (states are jug-amount pairs, not explicitly given nodes) - BFS applies just as validly here as to any explicitly-given graph, once you've correctly identified what the 'states' and 'moves' actually represent.

Find the minimum number of pour/fill/empty moves needed to measure out a target amount using two jugs. Brute force: Try every possible sequence of moves via DFS/backtracking, searching for the shortest one reaching the target - this can revisit the same jug-states repeatedly through different move orderings, far less efficient than BFS's guaranteed shortest-first exploration with visited tracking. Optimised: Modeling every possible (jugA, jugB) combination as a graph state and applying standard BFS treats this classic puzzle as exactly what it is - an unweighted shortest-path problem, where visited-state tracking prevents the search from wasting time revisiting already-explored jug configurations.

Model every reachable (amount in A, amount in B) pair as a node, with an edge for each of the six possible operations, and run a breadth-first search from the (0, 0) starting state using a visited set to avoid reprocessing states. Because BFS explores all states reachable in k moves before any state reachable in k+1 moves, the first time a state containing the target amount is dequeued is guaranteed to be reachable in the minimum number of moves. Since there are at most (a+1)*(b+1) distinct states and each has a constant number of outgoing moves, this visits the whole reachable state space only once. Time: O(a*b) Space: O(a*b)

Treat each state as (amount in jug A, amount in jug B) and explore all reachable states with a plain depth-first search over sequences of the six possible moves (fill, empty, or pour between the jugs), checking after every move whether either jug holds exactly the target. Without any bound on depth or any tracking of previously visited states, the same states get revisited endlessly and there is no guarantee the first solution found uses the minimum number of moves, so this only works as a bounded, illustrative exploration rather than a practical algorithm. Time: exponential (unbounded without pruning) Space: O(depth)

Repeatedly run a depth-limited depth-first search with an increasing move limit (1, 2, 3, ...), stopping as soon as some run of a given depth limit reaches a state containing the target amount. Because the search only succeeds once the depth limit reaches the true minimum number of moves, the first successful depth limit is guaranteed to be the answer, unlike plain DFS. This uses only as much memory as the current search depth, trading repeated re-exploration of shallow states (extra time) for a much smaller memory footprint than exploring the whole state space at once. Time: O(a*b*d) where d is the answer depth Space: O(d)

1. Model each (amount in jug A, amount in jug B) pair as a graph NODE, and each of the six possible moves (fill A, fill B, empty A, empty B, pour A into B, pour B into A) as an EDGE to another state. 2. BFS from the starting state (0, 0) finds the minimum number of moves to reach any state where either jug holds exactly the target amount. 3. Track visited states carefully - without it, moves like emptying an already-empty jug create self-loops that would make the BFS revisit the same states endlessly.

Time: O(a * b) - there are at most (a+1)*(b+1) distinct states, each visited at most once during the BFS. Space: O(a * b), for the visited-state tracking and the BFS queue.

Test target = 0 (zero moves needed), a target that isn't a multiple of gcd(a, b) (expect -1, since it's unreachable), and a, b at the upper bound of 1000.

Be ready to mention the classic number-theory shortcut (the target is reachable at all only if it doesn't exceed the larger jug's capacity and is a multiple of gcd(a,b)) as a quick way to short-circuit obviously-impossible cases before even running the BFS.