foxrivveg.c

类似早期农夫过河的问题 实现状态转换 保证兔子和蔬菜的存活

#include<stdio.h>
#include<stdlib.h>
struct ST {             //数据结构类型的定义
char S;           //元素的状态
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];                //定义访问数组，显示路径的二维数组
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邻接表的构造如下:\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;             //计数器限制狐狸，兔子，蔬菜的过河
if(Mode[i].fox!=Mode[j].fox) count++;
if(Mode[i].rabbit!=Mode[j].rabbit) count++;
if(Mode[i].vegetable!=Mode[j].vegetable) count++;        //状态不同则计数器加1
if((count<=1) && (Mode[i].people!=Mode[j].people) && (i!=j) )   //count限定三件物品，人的状态始终变化，两数组元素不能相同
{
   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");

//采用深度优先搜索遍历上面用邻接表结构存储的图，找出可行路径并输出
printf("\n深度优先搜索的结果如下:\n");
flag=0;
for(i=0;i<n;i++)     //非递归法求深度优先
 {
	stack[i]=0;     //初始化栈
	visit[i]=0;     //置全部顶点未访问标记
}
top=0;              //入栈一个元素
stack[top]=0; 
visit[0]=1;         //置已访问标记
/************/
for(j=0;j<2;j++) 
for(i=0;i<n;i++)path[j][i]=0;        //用二维数组存储不同的路径
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表示的状态还原为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");

}

}