cross zhe river.txt

第一次上转 有不完善的地方请大家指正

#include "stdio.h"
#include "stdlib.h"

#define MAX_STEP 100
/*商人数目，仆人数目的相反数，船的位置0此岸1对岸
b记录状态分五种情况*/
int a[MAX_STEP][3];
int b[MAX_STEP];
char *name[]=
{
"两个仆人",
"一个仆人",
"一商一仆",
"一个商人",
"两个商人",
};

void Search(int iStep)
{
int i;
/*如果已经达到目标，输出步骤*/
if(a[iStep][0]==0&&a[iStep][1]==0&&a[iStep][2]==1)
{

for(i=0;i<iStep;i++)
{
if(a[i][2]==0)
{ printf("%s到对岸\n",name[b[i]+2]);
}
else
{
printf("%s回此岸\n",name[b[i]+2]);
}
}
printf("\n");
getch();
return;
}
/*检测状态是否重复*/
for(i=0;i<iStep;i++)
{
if(memcmp(a[i],a[iStep],sizeof(a[i]))==0)
{
return;
}
}

/*检测商人是否有危险*/
if((a[iStep][0]+a[iStep][1]==0)||a[iStep][0]==0||a[iStep][0]==3);
else
{
return;
}


for(i=-2;i<=2;i++)
{
b[iStep]=i;
memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1]));/*记录各个状态*/
a[iStep+1][2]=1-a[iStep][2];
/*运送人数不能多与实际人数*/
if(i==0)
{
if(a[iStep][2]==0&&a[iStep][0]>=1&&a[iStep][1]<=-1)
{
a[iStep+1][0]=a[iStep+1][0]-1;
a[iStep+1][1]=a[iStep+1][1]+1;
Search(iStep+1);
}
else if(a[iStep][2]==1&&a[iStep][0]<=2&&a[iStep][1]>=-2)
{
a[iStep+1][0]=a[iStep+1][0]+1;
a[iStep+1][1]=a[iStep+1][1]-1;
Search(iStep+1);
}
continue;

}

if(a[iStep][2]==0&&a[iStep][0]>=i&&a[iStep][1]<=i)
{
a[iStep+1][i>0?0:1]=a[iStep][i>0?0:1]-i;
Search(iStep+1);
}
else if((a[iStep][2]==1)&&(3-a[iStep][0]>=i)&&(-3-a[iStep][1]<=i))
{
a[iStep+1][i>0?0:1]=a[iStep][i>0?0:1]+i;
Search(iStep+1);
}
}
}

void main()
{
a[0][0]=3;
a[0][1]=-3;
a[0][2]=0;
Search(0);
}