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