[week2]隐式图问题——倒水问题(BFS搜索法)

文章目录

题意

倒水问题 “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的小讲解

上一篇:031、Java中偶数偶数的判断方法


下一篇:PTA团体程序设计天梯赛-练习集L1-031 到底是不是太胖了