#include<stdio.h>
#include<string.h>
#define N 3   //酒杯数
#define MAX_SIZES 100  //状态表中的最大状态数


 typedef struct node //边节点
{
    int adjvex;   //邻接点的位置
    node*next;  //指向下一个节点
}ARCNODE;  //邻接表中的结点类型

 typedef struct   //顶点节点
{  
    int vexdata[N];        //各酒杯的存储状态
    ARCNODE*next;      //指向下一个邻接点
}VEXNODE;//表头结点类型

 int A[MAX_SIZES];//用于存储路径的数组
int top=0;//数组中的个数 
int full[N];//各酒杯的最大容量 
int part[N];//各酒杯的当前容量 
int end[N];//最终状态

 VEXNODE s[MAX_SIZES];  //状态表
int sta;//状态表当前状态数 
  
 int sum=0;//所有解的个数
int end_vex;//结束的状态点 
bool visited[MAX_SIZES];//标记状态是否被访问
   
  
 bool compare(int a[],int b[])   //比较状态
  {  
    int i;  
    for(i=0;i<N;i++) 
        if(a[i]!=b[i])  
          return true;//两数组不相等，返回true 
    return false;//相等，返回false 
  } 
  void save(int number)  
 {   //保存状态,如果状态存在则仅仅加入领接表,如果不存在则加入状态表，并加入邻接表
     ARCNODE*p; 
     int i;  
     for(i=0;i<=sta;i++) 
     {  
        if(!compare(part,s[i].vexdata));  
             break;//该状态存在，跳出for循环
     } 
  
     if(i>sta)//将该状态加入状态表
     {  
        sta++; 
        for(int j=0;j<N;j++) 
        s[sta].vexdata[j]=part[j]; 
        s[sta].next=NULL;  
        if(!compare(part,end))  
           end_vex=sta;//该状态是最终状态，记住在状态表中的位置
     } 


     p=new ARCNODE; 
     p->adjvex=i;  
     p->next=s[number].next;  
     s[number].next=p;//加入邻接表
  } 
  
 void jisuan(int number)//求出某状态的所有邻接点
{  
    int i,j,I,J;  
    for(i=0;i<N;i++)//编号为i的酒杯与其他酒杯交换
    {   
        for(j=0;j<N;j++) 
       {  
            if(j==i)     continue;//同一酒杯，无法变换
            I=part[i];//保存i酒杯的当前的容量
            J=full[j]-part[j];//j酒杯的空闲量
               if(I<=J)//若i酒杯的当前容量小于等于j酒杯的空闲量 
               {  
                part[i]=0;  
                part[j]+=I;//将i酒杯的酒倒向j酒杯  
                save(number);//调用save()函数，保存当前的状态
                part[i]=I;  
                part[j]-=I;//恢复各酒杯的原始状态
               }  
           else//若i酒杯的当前容量大于j酒杯的空闲量
           {  
                part[i]-=J;  
                part[j]=full[j];//把j酒杯加满  
                save(number);//调用save()函数，保存当前的状态
                part[i]+=J;  
                part[j]-=J;//恢复各酒杯的原始状态
           } 
        } 
    } 
 } 
 
  
 void create()//建立状态的函数 
{  
    int i;
    int number=i; 
 printf("输入各个酒杯的容积:"); 
    for(i=0;i<N;i++)      
     scanf("%d",&full[i]); 
 printf("输入对应酒杯的起始状态:"); 
    for(i=0;i<N;i++)  
 scanf("%d",&s[0].vexdata[i]);//初始状态即状态表中的s[0] 

 printf("输入对应酒杯的最终状态:"); 
    for(i=0;i<N;i++) 
     scanf("%d",&end[i]);//所求的状态
    number=0; sta=0;   
      s[0].next=NULL; 
  
    while(number<=sta) 
    {      
        for(i=0;i<N;i++) 
          part[i]=s[number].vexdata[i];//将s[number]的状态赋给各酒杯当前的容量  
          jisuan(number);//调用jisuan(),求出该状态所有的邻接点
          number++; 
    } 
    
    for(number=0;number<=sta;number++) 
         visited[number]=false; 
 } 
  
 void prtf()   //输出路径 
{  
 int i,j,k; 
 printf("方案%d:\n",sum);  
    for(i=0;i<top;i++) 
    {  printf(" ");  
        j=A[i];//路径中的位置
        for(k=0;k<N;k++) 
        printf("%d",s[j].vexdata[k]);//输出该状态
    printf(" "); 
   }  
 printf("\n"); 
 } 
 
  
 void dfs(int v0)//深度优先搜索遍历函数 
{  
  if(!visited[v0])//判断该状态是否被访问过
   {  
        if(v0==end_vex)//判断该状态是否是最终状态
        {  
            sum++;  
           prtf();//调用输出函数
        }  
        else//若不是，深度搜索
        {  
            ARCNODE *p; 
            p=s[v0].next;  
            visited[v0]=true;//标记该状态已访问
           while(p) 
           {  
              A[top++]=p->adjvex;   //记录路径
              dfs(p->adjvex);//递归调用遍历函数
              A[--top];//清空路径
              p=p->next; 
            }  
           visited[v0]=false;//标记该状态未访问，用于其它路径中访问

        } 
  } 
 } 
  
 void findpath() 
 {  
    A[top++]=0;         //选择深度所搜遍历的起点
    dfs(0);           //进行深度所搜遍历 
} 
  
 void  main()  
 {int i,k;  
    create();        //建立模型的状态 
printf("状态表中的%d中状态：\n",sta+1); 
    for(i=0;i<=sta;i++) 
   {for(k=0;k<N;k++)  
     printf("%d",s[i].vexdata[k]); 
     printf("\t"); 
    }  
    printf("\n共得到如下解法:\n");  
    findpath();              //输出得到的解 
}