← 返回 bytedance 的题目列表Water Jug: Reachability and Shortest Operation Sequence
类型：online_judge
Two Jugs (Reachability + Shortest Operation Sequence)
You are given two jugs with capacities x and y. Water supply is unlimited and both jugs start empty. You may repeatedly perform the following operations:
Fill one jug to its full capacity.
Empty one jug (set it to 0).
Pour water from one jug to the other until the source becomes empty or the destination becomes full.
Given a target volume z:
Tasks
Decide whether there exists a sequence of operations such that at some step either jug contains exactly z units of water (if not specified, assume the condition is “either jug equals z”; you may clarify whether “sum equals z” is also acceptable).
If reachable, return the minimum number of operations and one shortest operation sequence; otherwise report unreachable.
Suggested I/O
Input: three integers x y z
Output:
If unreachable: false
If reachable: true, the minimum steps k, and a shortest operation list describing each move.
Constraints
0 <= x, y, z <= 10^3 (suitable for BFS shortest path)
Examples / Tests
Input: 3 5 4 -> true (with a shortest sequence)
Input: 2 6 5 -> false
Input: 1 1 1 -> true
Input: 0 5 5 -> true
Input: 0 5 3 -> false
Example
Input
3 5 4
Output
true
6
fill B
pour B->A
empty A
pour B->A
fill B
pour B->A