xdsyyr.c

野人与修道士问题 这是一个古典的问题.假设有n个修道士和n个野人准备渡河,但只有一条能容纳c人的小船,为了防止野人侵犯修道士,要求无论在何处,修道士的个数不得少于野人的人数(除非修道士个数为0)

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

/////////////////////////////////////////////////////////////////////
typedef struct 
{
 int xds;//修道士
 int ymr;//野蛮人
 int zt;//状态
}DataType;

typedef struct Node
{
 int dest;
 struct Node *next;
}Edge;

typedef struct
{
 DataType data;
 int sorce;
 Edge *adj;
 int pre;//指向此点的点的序号
}AdjLHeight;

typedef struct
{
 AdjLHeight a[10000];
 int numOfVerts;
 int numOfEdges;
}AdjLGraph;
//////////////////////////////////////////////////////////////////
void AdjInitiate(AdjLGraph *G)
{
 int i;

 G->numOfEdges=0;
 G->numOfVerts=0;
 for(i=0;i<10000;i++)
 {
  G->a[i].sorce=i;
  G->a[i].adj=NULL;
  G->a[i].data.zt=-1;
  G->a[i].pre=-1;
 }
}

void AdjDestroy(AdjLGraph *G)
{
 int i;
 Edge *p,*q;
 for(i=0;i<G->numOfVerts;i++)
 {
  p=G->a[i].adj;
  while(p!=NULL)
  {
   q=p->next;
   free(p);
   p=q;
  }
 }
}

void InsertVertex(AdjLGraph *G, int i, DataType vertex)
{
 if( i>=0 && i<10000 )
 {
  G->a[i].data.xds=vertex.xds;
  G->a[i].data.ymr=vertex.ymr;
  G->a[i].data.zt=vertex.zt;
  G->numOfVerts++;
 }
 else printf("结点越界!\n");
}

void InsertEdge(AdjLGraph *G,int v1,int v2)
{
 Edge *p;
 if(v1<0||v1>=G->numOfVerts||v2<0||v2>G->numOfVerts)
 {
  printf("参数v1或v2越界出错!");
  exit(0);
 }
 p=(Edge *)malloc(sizeof(Edge));
 p->dest=v2;
 p->next=G->a[v1].adj;
 G->a[v1].adj=p;
 G->numOfEdges++;
}

////////////////////////////////////////////////////////////////////

 int n,c;
 DataType fa[10000];
////////////////////////////////////////////////////////////////////


int jiancha(DataType x)     //检查当前情况下，修道士是否安全
{
    if ((x.xds>=x.ymr||x.xds==0)&&((n-x.xds)>=(n-x.ymr)||x.xds==n)&&x.xds>=0&&x.xds<=n&&x.ymr>=0&&x.ymr<=n)
       return 1;
    else
       return 0;
}

int findfa(DataType x)     //生成在船上修道士仍安全的几种情况；
{
 int i=0,a,b,t=0;
 if(x.zt)
 {
  a=0;b=c-a; 
  while (a+b>=1)
   {
    t++;
    while (b>=0)
    {
     
     fa[i].xds=a;
     fa[i].ymr=b;
     i++;
     a++;
     b--;
    }
    a=0;
    b=c-a-t;
   }
 }
 else
 {
  a=1;b=0;t=0;
  while (a+b<=c)
  {
   t++;
   while (a>=0)
   {     
    fa[i].xds=a*(-1);
    fa[i].ymr=b*(-1);
    i++;
    a--;
    b++;
   } 
   a=fa[0].xds*(-1)+t;
   b=0;
  }
 }
 return i; 
}


int print(AdjLGraph *p,int g)     //打印安全渡河的过程
{
    DataType b[1000];
    int i=0;
    while (g!=-1)
    {
       b[i++]=p->a[g].data;
       g=p->a[g].pre;
    }

    while ((--i)>-1)     
    {
          printf("( %d %d %d )",b[i].xds,b[i].ymr,b[i].zt);
          if (!(b[i].xds==0&&b[i].ymr==0&&b[i].zt==0)) 
          {
     if (b[i].zt==1)
   printf(" → ( %d %d ) → ( %d %d 0 )\n",b[i].xds-b[i-1].xds,b[i].ymr-b[i-1].ymr,b[i-1].xds,b[i-1].ymr);
   else printf(" ← ( %d %d ) ← ( %d %d 1 )\n",(b[i].xds-b[i-1].xds)*(-1),(-1)*(b[i].ymr-b[i-1].ymr),b[i-1].xds,b[i-1].ymr);
          }
          else printf("\n");    
    }
    printf("渡河成功!\n");
    
 return 1;
}

void work(AdjLGraph *p)//广搜建立表
{
 DataType tem;
 int i,flag1,g=0,j,count=0,k=0,t;
 while (p->a[k].data.zt!=-1)
 {
        j=findfa(p->a[k].data);
        for (i=0;i<j;i++)
  {
   tem.xds=p->a[k].data.xds-fa[i].xds;
   tem.ymr=p->a[k].data.ymr-fa[i].ymr;
   tem.zt=1-p->a[k].data.zt;
   if (jiancha(tem))
   {
    flag1=1;
    t=k;
                while (t!=-1)
    {
     if(tem.xds==p->a[t].data.xds&&tem.ymr==p->a[t].data.ymr&&tem.zt==p->a[t].data.zt)
     {
      flag1=0;
         break;                
     }
     t--;
    }
   
                if(flag1==1)
    {
     
     g++;
     p->a[g].pre=k;
     InsertVertex(p,g,tem);
     InsertEdge(p,k,g);
     if (tem.xds==0&&tem.ymr==0&&tem.zt==0)
     {
      count++;
      print(p,g);
     }
    }
   }
  }
  k++;
 }  

 if (count==0)
  printf("不能渡河!\n");
 else
  printf("有%d种渡河方式。\n",count);
}

////////////////////////////////////////////////////////////////

main()
{
 AdjLGraph G;
 DataType first;
 
 while(1)
 {
  printf("请输入野蛮人和修道士人数N:");
  scanf("%d",&n) ;
  if(n==0) break;
  printf("请输入船可乘人数C:");
  scanf("%d",&c) ;
  AdjInitiate(&G);
  first.xds=n;
  first.ymr=n;
  first.zt=1;
  InsertVertex(&G, 0, first);

  work(&G);
 
  AdjDestroy(&G);
 }
  system("pause");

}