Problem4803--水缸灌水

4803: 水缸灌水

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

有两个无刻度标志的水壶,分别可装 $x$ 升和 $y$ 升($x,\ y$ 为整数,$x,\ y \leq 100$)的水。
设另一方面有一水缸,可用来向水壶灌水或倒出水,两水壶间,水也可以相互倾灌。
已知 $x$ 升为满壶,$y$ 升为空壶。问如何通过倒水或灌水操作用最少步数能在 $y$ 升壶中量出 $z\ (z \leq 100)$ 升的水来。

Input

一行:$x,\ y,\ z$。

Output

每一行为一个步骤,输出步骤数和 $x,\ y$ 水壶里面的水(输出时注意:本着节约用水的原则,因此,优先两个水壶互相倒水,无法达到目的时,再考虑,将水浪费掉)
如果无解则输出
No answer!

Sample 1 Input

8 5 3

Sample 1 Output

sep0: 8 0
sep1: 3 5
sep2: 3 0
sep3: 0 3

HINT

这道题与一般的水缸灌水有一定区别,一般的水缸灌水只需要输出需要的最小步数而这道题需要输出每一步的水壶中的水量并且要节约用水(我做的时候被坑得要死)。
 根据题意我们可以看出一共有六种情况:
1、a壶倒空,
2、b壶倒空,
3、a壶倒满,
4、b壶倒满
5、a壶倒入b壶中(1)b壶倒满,a壶没有剩余(2)b壶倒满,a壶有剩余
6、b壶倒入a壶中(1)a壶倒满,b壶没有剩余(2)a壶倒满,b壶有剩余
 通过这六种情况可以建立一个函数,把这六步遍历一遍即可。
 ————————————————
版权声明:本文为CSDN博主「Y_sofun」的原创文章,遵循CC 4.0 by-sa版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/Y_sofun/article/details/54971572

Source/Category

基础算法 4.100.BFS