例7-3 倒水问题。

有装满水的6升的杯子、空的3升杯子和1升杯子，3个杯子中都没有刻度。在不使用其他道具的情况下，是否可以量出4升的水呢？

方法如图7-7所示。

图7-7  倒水问题：一种方法是(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）。

 

学习点：

有时候用数组队列保存路径时更方便，记录前驱的数组编号即可。通过对操作编码，记录last_op，打印操作步骤。

 

#include
     
      #include
      
       #include
       
        using namespace std;#define MAXN 105int cap[3], x;int vis[MAXN][MAXN];struct Node {  int v[3];  int fa, dist, last_op;};Node q[MAXN*MAXN];void print_path(int idx) {  if(q[idx].fa != idx) {    print_path(q[idx].fa);      printf("%d -> %d\n", q[idx].last_op/10, q[idx].last_op%10);  }  printf("%d %d %d\n", q[idx].v[0], q[idx].v[1], q[idx].v[2]);}void bfs() {  int front=0, rear=1, i, j, k;  q[0].v[0] = cap[0];  q[0].v[1] = q[0].v[2] = q[0].dist = q[0].fa = 0;  vis[0][0] = 1;  while(front