#include<stdio.h> 
#include <stdlib.h>
#define N 100 
#define BUCKETS 3
struct ele{ 
int state[BUCKETS]; /*各桶盛油量*/ 
int sbucket; /*源桶*/ 
int obucket; /*目標桶*/ 
int last; /*軌跡元素在隊列中的下標*/ 
}q[N]; /*隊列*/ 
int full[BUCKETS]; 
int i,j,k,found,unable,wi,wj,v,targ; 
int head,tail; 
void main() 
{ 
/*輸入各桶容量和目標容量*/ 
printf("Enter volume of buckets.\n"); 
for(i=0;i<BUCKETS;i++) 
scanf("%d",&full[i]); 
/*如要檢查full[0]>full[1]>full[2],相應代碼在此*/ 
printf("Enter volume of targ.\n"); 
scanf("%d",&targ); /*檢查targ<=full[0]的代碼在此*/ 
/*設置將初始狀態存入倒油狀態隊列等初值*/ 
q[0].state[0]=full[0]; 
for(i=1;i<BUCKETS;i++) 
q[0].state[i]=0; 
q[0].sbucket=0; 
q[0].obucket=0; 
q[0].last=0; 
found=unable=0; 
head=tail=0; 
do 
{ 
/*對狀態隊列中第一個還未檢查過的元素在還未檢查完每個倒出的桶 
且還未找到解且還未確定無解情況下循環*/ 
for(i=0;i<BUCKETS&&!found&&!unable;i++) 
if(q[head].state[i]>0) /*倒出桶有油*/ 
/*在還未檢查完每個油桶且還未找到解且還未確定無解情況下循環*/ 
for(j=0;j<BUCKETS&&!found&&!unable;j++) 
if(j!=i&&q[head].state[j]<full[j]) 
{ /*當前桶不是倒出桶且桶還有空*/ 
/*確定本次倒油量*/ 
if(q[head].state[i]>full[j]-q[head].state[j]) 
v=full[j]-q[head].state[j]; 
else v=q[head].state[i]; 
wi=q[head].state[i]-v; 
wj=q[head].state[j]+v; 
/*在隊列中檢查倒油后的結果狀態是否在隊列中出現*/ 
for(k=0;k<=tail;k++) 
if(q[k].state[i]==wi&&q[k].state[j]==wj) break; 
if(k>tail) /*結果狀態不在隊列中出現*/ 
{ 
/*將結果狀態和軌跡信息存入隊列*/ 
tail++; 
q[tail].state[i]=wi; 
q[tail].state[j]=wj; 
q[tail].state[3-i-j]=q[head].state[3-i-j]; 
q[tail].sbucket=i+1; 
q[tail].obucket=j+1; 
q[tail].last=head; 
/*如有桶達到目標盛油量，則設置找到解標志*/ 
if(wi==targ||wj==targ)found=1; 
} 
} 
if(!found) /*還未找到解*/ 
{ 
head++; /*修正隊列第一個還未檢查過元素指針*/ 
if(head>tail) /*隊列中的元素都已檢查過*/ 
unable=1; /*設置無解標志*/ 
} 
}while(!found&&!unable); /*還未找到解且還未確定無解*/ 
if(found) /*找到解*/ 
{ 
/*根據倒油步聚的軌跡信息，形成倒油步聚序列*/ 
i=tail; 
j=-1; 
do /*原倒油步聚逆向鏈接，現改為正向鏈接*/ 
{ 
k=q[i].last; 
q[i].last=j; 
j=i; 
i=k; 
}while(j); 
/*輸出倒油步聚序列*/ 
for(k=q[k].last;k>=0;k=q[k].last) 
{ 
printf("%5d to %2d:",q[k].sbucket,q[k].obucket); 
for(i=0;i<BUCKETS;i++) 
printf("%4d",q[k].state[i]); 
printf("\n"); 
} 
system("pause");
} 
else printf("Unable!\n"); 
}