好久没来，有时真想休学一年，好好学学算法，离散数学等。
今天来请交大神们，是在算法书上看到的。

题目是：
有装满水的6升的杯子、空的3升杯子和1升杯子，3个杯子中都没有刻度。在不使用其他道具的情况下，是否可以量出4升的水呢？倒水问题的一种方法为：
                      (6,0,0)->(3,3,0)->(3,2,1)->(4,2,0)
   注意：由于没有刻度，用杯子x给杯子y倒水时必须一直把杯子y倒满或者把杯子x倒空，而不能中途停止。
你的任务是解决一般性的问题：设大、中、小3个杯子的容量分别为a,b,c，最初只有大杯子装满水，其他两个杯子为空。最少需要多少步才能让某一个杯子中的水有x升呢？(0<c<b<a<1000)。

Input
   输入数据包括多组数据，每组数据占一行，分别为a,b,c,x，四个数间用一个空格隔开。

Output
   每行输入对应一行输出，即完成目标所需的最小步数。如果不能完成目标，输出"NO"。

Sample Input
6 3 1 4
9 6 3 1

Sample Output
3
NO



我的基本思路是，建立的模型是个树形结构，从头结点开始状态为（a，0，0）。然后用队列按照层拓展下去，这样应该可以求出最少步骤吧？
但是书上分析的是图模型，而且有点不明白边数不超过6*10^6是怎么估算出来的，我只知道结点数是不会超过10^6？？求解~

这个问题在这里讨论了太多次了。该问题的模型是图，而且是有向图，不是树。只不过应用其上的最短路径搜索算法在搜索过程中去掉了其中的环，相当于广度优先遍历树。

关于节点和边的估算，你的值还是有点粗糙。三个瓶子，每个瓶子的容积是整数升，最多1000升水，抛开倒法不管，最多相当于把1000份相同的水装进3个不同的瓶子里，这不是组合数学里的经典命题么，共有C(1002,2)=501501种。而实际上远比这少。一个状态下可能的倒水方式最多6种(那三个瓶子来回倒呗)，也就是每个节点最多6条边，又因为是有向图，所以总边数最多为节点数乘6。

这道原题我好像就做过，好像还在论坛里帖了代码。在百度里搜我的名字加倒水保不齐就能找到。

谢谢B版了，搜到了。先保存下来。大概浏览下，好简短，觉得思路应该特别清晰，佩服你的功力啊，明天再看，小菜我自己先写写。

还真没搜到%%…………

你肿么搜的？求指教搜索方法￥##￥%……

呃，其实我也想知道楼主搜到的是哪一篇

https://bbs.bccn.net/viewthread.php?tid=359744&extra=&page=2

不过B版的代码无法编译过啊~。

b版什么时候在线啊，我把自己写的代码贴出来，能不能赐教。加了大量注释了，不知道有还有没有什么错。