文章目录
题意
倒水问题 “fill A” 表示倒满A杯,"empty A"表示倒空A杯,“pour A B” 表示把A的水倒到B杯并且把B杯倒满或A倒空。
Input
输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A <= B 、C <= B <=1000 、A和B互质。
Output
你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始,不应该有空行或任何尾随空格。
输入样例
2 7 5
2 7 4
输出样例
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success
分析
隐式图问题
已知起始状态和结束状态,以及状态变化的条件,求从起始变化到结束状态的过程。
- 为什么用BFS?
这种问题实际上是按照要求扩展节点(寻找当前节点的连接节点),找到目标节点,将中间隐藏的过程展示出来。这与BFS搜索算法的本质相同。
BFS的小讲解