#include<stdio.h>
#include<stdlib.h>
struct ST {             //數(shù)據(jù)結(jié)構(gòu)類型的定義
char S;           //元素的狀態(tài)
int people;       
int fox;
int rabbit;
int vegetable;
};

struct List             //鄰接表的定義
{
  int data;
  struct List *next;
};

void main()
{
int count,i,j,flag,max,temp,n=10;
int visit[10],path[2][10];                //定義訪問數(shù)組，顯示路徑的二維數(shù)組
int stack[10],top;                        //定義順序棧，和top指針表示棧頂元素
struct List *list[10],*p,*q;
struct ST Mode[10]={{'a',0,0,0,0},{'b',0,0,0,1},{'c',0,0,1,0},{'d',0,1,0,0},{'e',0,1,0,1},
{'f',1,0,1,0},{'g',1,0,1,1},{'h',1,1,0,1},{'i',1,1,1,0},{'j',1,1,1,1}};

printf("********************************************\n");
printf("程序說明：a=0000,b=0001,c=0010,d=0100,e=0101,f=1010,g=1011,h=1101,i=1110,j=1111\n");
printf("0表示在河此岸，1表示在河對岸\n例如f=1010:表示人在對岸，狐貍在此岸，兔子在對岸，蔬菜在此岸\n");

system("pause");

//建立鄰接表
printf("\n鄰接表的構(gòu)造如下:\n");
for(i=0;i<n;i++)
{
list[i]=(struct List *)malloc(sizeof(struct List));     //初始化鄰接表
list[i]->data=i;
list[i]->next=NULL;
p=(struct List *)malloc(sizeof(struct List));
list[i]->next=p;
p->data=i;
p->next=NULL;
for(j=0;j<n;j++)
{count=0;             //計(jì)數(shù)器限制狐貍，兔子，蔬菜的過河
if(Mode[i].fox!=Mode[j].fox) count++;
if(Mode[i].rabbit!=Mode[j].rabbit) count++;
if(Mode[i].vegetable!=Mode[j].vegetable) count++;        //狀態(tài)不同則計(jì)數(shù)器加1
if((count<=1) && (Mode[i].people!=Mode[j].people) && (i!=j) )   //count限定三件物品，人的狀態(tài)始終變化，兩數(shù)組元素不能相同
{
   q=(struct List *)malloc(sizeof(struct List));
   p->next=q;
   p=q;
   p->data=j;
   p->next=NULL;
   }
}
}
//打印鄰接表
for(j=0;j<n;j++)
{
p=list[j]->next;
while(p!=NULL){
printf("%c--",Mode[p->data].S);
p=p->next;
}
printf("\n");
}

system("pause");

//采用深度優(yōu)先搜索遍歷上面用鄰接表結(jié)構(gòu)存儲的圖，找出可行路徑并輸出
printf("\n深度優(yōu)先搜索的結(jié)果如下:\n");
flag=0;
for(i=0;i<n;i++)     //非遞歸法求深度優(yōu)先
 {
	stack[i]=0;     //初始化棧
	visit[i]=0;     //置全部頂點(diǎn)未訪問標(biāo)記
}
top=0;              //入棧一個元素
stack[top]=0; 
visit[0]=1;         //置已訪問標(biāo)記
/************/
for(j=0;j<2;j++) 
for(i=0;i<n;i++)path[j][i]=0;        //用二維數(shù)組存儲不同的路徑
j=0;
temp=0;
while(top>-1 && temp!=2)            //求第一條路徑
{
p=list[stack[top]]->next->next;

if(p!=NULL && visit[p->data]==0)
{
if(p->data==n-1)
		{
		for(i=0;i<=top;i++)
		{printf("%c--",Mode[stack[i]].S);path[temp][i]=stack[i];}
		printf("%c\n",Mode[n-1].S);path[temp][i]=n-1;max=i;
		flag=1;
		top--;
		continue;
		}
else{
      top++;
      stack[top]=p->data;
      visit[stack[top]]=1;
      continue;
      }

}

while(p!=NULL && visit[p->data]==1)         //求第二條路徑
{
		 p=p->next;
     if(p==NULL)
		 {
                 for(i=0;i<n;i++)
		 visit[i]=0;
		 for(i=0;i<=top;i++)
		 visit[stack[i]]=1;
                 top--;
                 break;
		 }
      if(p!=NULL && visit[p->data]==0)
		 {
		 if(p->data==n-1) {
		 for(i=0;i<=top;i++) 
               {printf("%c--",Mode[stack[i]].S);path[temp][i]=stack[i];}
		 printf("%c\n",Mode[n-1].S);path[temp][i]=n-1;max=i;
		 flag=1;
		 top--;
                 temp++;
	         break;}
                
 else{
		 top++;
		 stack[top]=p->data;
		 visit[stack[top]]=1;
		 break;}
                 }
}
}

system("pause");

//輸出路徑，將a到j(luò)表示的狀態(tài)還原為0、1組合，再打印出文字顯示的路徑
if(flag==0) printf("\n沒有可以過河的方法!");
if(flag==1)
{
printf("\n\n過河的方案如下:\n");
for(temp=0;temp<2;temp++)
{
printf("\n[%d]\n",temp+1);
for(i=0;i<=max;i++){
if(Mode[path[temp][i]].people==0)printf("人 ");
if(Mode[path[temp][i]].fox==0)printf("狐貍 ");
if(Mode[path[temp][i]].rabbit==0)printf("兔子 ");
if(Mode[path[temp][i]].vegetable==0)printf("蔬菜 ");
printf("================");
if(Mode[path[temp][i]].people==1)printf("人 ");
if(Mode[path[temp][i]].fox==1)printf("狐貍 ");
if(Mode[path[temp][i]].rabbit==1)printf("兔子 ");
if(Mode[path[temp][i]].vegetable==1)printf("蔬菜 ");
printf("\n");
}
}

system("pause");

}

}