农夫过河农夫要带狼、羊、草过河,但船每次只能容纳农夫和一样东西,如果农夫不在狼会吃羊,羊会吃草.求算法.

Question

农夫过河
农夫要带狼、羊、草过河,但船每次只能容纳农夫和一样东西,如果农夫不在狼会吃羊,羊会吃草.求算法.

Answer 1

运行结果如下：
带羊到对岸
空手回本岸
带狼到对岸
带羊回本岸
带菜到对岸
空手回本岸
带羊到对岸
带羊到对岸
空手回本岸
带菜到对岸
带羊回本岸
带狼到对岸
空手回本岸
带羊到对岸
以上是找出的所有解,共有两个解.
程序如下：
#include
#include
#include
#define MAX_STEP 20
//index:0 - 狼,1－羊,2－菜,3－农夫,value：0－本岸,1－对岸
int a[MAX_STEP][4];
int b[MAX_STEP];
char *name[] =
{
"空手",
"带狼",
"带羊",
"带菜"
};
void search(int iStep)
{
int i;
if (a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4)
{
for (i = 0; i < iStep; i++)
{
if (a[i][3] == 0)
{
printf("%s到对岸\n",name[b[i] + 1]);
}
else
{
printf("%s回本岸\n",name[b[i] + 1]);
}
}
printf("\n");
return;
}
for (i = 0; i < iStep; i++)
{
if (memcmp(a[i],a[iStep],sizeof(a[i])) == 0)
{
return;
}
}
if (a[iStep][1] != a[iStep][3] && (a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1]))
{
return;
}
for (i = -1; i