求助：农夫过河如何解决？
农夫过河。一个农夫带着一只狼，一只羊和一些菜过河。河边只有一条船，由于船太小，只能装下农夫和他的一样东西。在无人看管的情况下，狼要吃羊，羊 要吃菜，请问农夫如何才能使三样东西平安过河。打印出过河方案？？？？？？
老师的提示为：
分析题意：
将问题数字化。用１代表狼，２代表羊，３代表菜。则在河的某一边物体的分布有以下８种情况。
物体个数0123
分布情况01231，21，32，3代码之和01233456
是否相克0相克相克
当（两物体在一起而且）代码和为３或５时，必然是相克物体在一起的情况。
[解决办法]
第一趟把羊拉过去
空船回来
第二趟把菜来过去
把羊拉回来
第三趟把狼拉过去
空船回来
第四趟把羊拉过去
结束程序
应该采用回溯算法
就是用循环进行判断
当条件不满足时
就进行下一个循环
程序自己写吧
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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 <= 2; i++)
{
b[iStep] = i;
memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1]));
a[iStep + 1][3] = 1 - a[iStep + 1][3];
if (i == -1)
{
search(iStep + 1);
}
else if (a[iStep][i] == a[iStep][3])
{
a[iStep + 1][i] = a[iStep + 1][3];
search(iStep + 1);
}
}
}
int main()
{
search(0);
return 0;
}
