1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 /*下面定义结点的类型*/ 5 #define Min(a,b) ((a>b)?b:a) 6 //宏定义的操作符Min作用 取最小值; 7 const int MAX=1010; 8 //解答树的结点最多 9 typedef struct Node 10 { 11 int v[3];//三个杯子的剩余水量; 12 int fa;//第一次访问到这个结点是的前一个结点的下标； 13 //通过下标可以随机访问真不错; 14 int last_op;//记录从上个结点到这个结点的变化方式 15 //last_op认为是两位数字,第一位表示往外倒水的杯子 16 //的编号,第二位表示被倒入水的杯子; 17 int deepth; 18 //记录从原始状态到这个状态变化的最少的步数;也就是解答树的深度； 19 }Node; 20 int cup_capacity[3];//存储三个杯子的容量； 21 int water_to_get; //存储要量出的水量; 22 Node q[MAX*MAX]; //定义这么多个状态组成的数组; 用这个数组来表示队列真不错; 23 int vis[MAX][MAX];//两个下标分别是中杯的余量和小杯的余量; 24 void print_path(int destination);//函数的作用是输出从下标为0到下标为destination的结点的路径; 25 void bfs();//breath-first-search;广度优先遍历 ; 26 int main() 27 { 28 /*首先读入三个杯子的容量和要量出的水量*/ 29 scanf("%d%d%d%d",&cup_capacity[0],&cup_capacity[1],&cup_capacity[2],&water_to_get); 30 /*进行遍历搜索*/ 31 memset(vis,0,sizeof vis);//sizeof 对于变量名可以不用括号 表明 它并不是一个函数 ; 32 /* 33 memset()起初是为字符数组赋值的所以需要包含头文件string.h， 34 但是它可以为结构体，一维数组，二维数组等赋值了 ; 35 这里其实并不需要赋值，因为全局变量已经被初始化了; 36 */ 37 bfs(); 38 return 0; 39 } 40 void bfs() 41 { 42 q[0].v[0]=cup_capacity[0]; 43 q[0].v[1]=q[0].v[2]=0; 44 q[0].fa=0;//因为第一个结点没有父节点了; 45 q[0].deepth=0;//也可以不写这些0;因为全局变量会自动初始化; 46 q[0].last_op=0;//因为是第一个结点 ; 47 vis[q[0].v[1]][q[0].v[2]]=1;//表示这个结点已经在队列里了 48 //如果在遇到它就不再将它放进队列了; 49 //上个句子也可以这么写vis[0][0]=1; 50 int front=0,rear=1;//模拟队列;可以实现广度优先遍历; 51 while(front<rear) 52 { 53 Node N=q[front];//当前队列中将要访问的变量; 54 if(N.v[0]==water_to_get||N.v[1]==water_to_get||N.v[2]==water_to_get) 55 {//如果当前结点正好就是要访问的,那么就来输出它的路径; 56 //首先输出需要的步数; 57 printf("%d\n",N.deepth); 58 //然后调用递归函数依次输出各个中间状态; 59 print_path(front); 60 return; 61 } 62 for(int i=0;i<3;i++)//往外倒水的杯子进行枚举; 63 { 64 65 for(int j=0;j<3;j++)//被倒入水的杯子的枚举; 66 {//i！=j;是避免了那些自己往自己里面倒水的情况发生; 67 Node &IN=q[rear]; 68 if(i==j)continue; 69 int amount=Min(N.v[i],cup_capacity[j]-N.v[j]);//这个是用来决定倒出水的多少 70 //要么倒水的杯子倒完；要么被倒入的杯子被倒满; 71 for (int k=0;k<3;k++) 72 { 73 IN.v[k]=N.v[k]; 74 } 75 IN.v[i]=N.v[i]-amount;//从i杯倒出amount量的水； 76 IN.v[j]=N.v[j]+amount;//倒入j杯amou量的水; 77 //至此就产生了一个状态；然后就要看它是否已经存在于队列里面了; 78 if(!vis[IN.v[1]][IN.v[2]]) 79 { 80 vis[IN.v[1]][IN.v[2]]=1; 81 IN.fa=front;//设置父节点的下标； 82 IN.deepth=N.deepth+1;//设置最少步骤数； 83 IN.last_op=10*i+j;//记录变换的方法; 84 85 rear++; 86 }//if 87 } //for(j) 88 } //for(i) 89 front++;//从队列的下一个结点向下一次考察; 90 91 }//while 92 } 93 void print_path(int destination) 94 { 95 if(q[destination].fa!=destination) 96 { 97 print_path(q[destination].fa);//先找到原始的元素;递归栈机制可以记得路径 98 int from=q[destination].last_op/10,to=q[destination].last_op%10; 99 int num=q[q[destination].fa].v[from]-q[destination].v[from]; 100 printf("cup %d (-%d)->cup %d\n",from,num,to); 101 } 102 printf("(%d,%d,%d)\n",q[destination].v[0],q[destination].v[1],q[destination].v[2]); 103 104 }