农夫过河问题

Question

一个农夫带着—只狼、一只羊和—棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和—件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。
实现上述求解的搜索过程可以采用两种不同的策略：一种广度优先搜索，另一种深度优先搜索。这里介绍在广度优先搜索方法中采用的数据结构设计。
用状态表，程序应在屏幕上得到如表3所示的结果。
表3 测试结果
步骤 状态
南岸 北岸
0 农夫 狼 羊 白菜
1 狼 白菜 农夫 羊
2 狼 农夫 白菜 羊
3 农夫 狼 羊 白菜
4 羊 农夫 狼 白菜
5 农夫 羊 狼 白菜
6 农夫 狼 羊 白菜

请留下你的QQ，我只学了2个月，不会做，请教
我问的是用java，使用广度优先搜索

Answer 1

这个问题我做过 （假设农夫现在的位置是A 对岸是B）
农夫 狼 羊 白菜的问题
首先农夫和羊先到B
接着农夫一人回到A（羊在B）
然后农夫和白菜到B（此时农夫和羊和白菜都在B）
之后农夫和羊到A（只有白菜在B）
然后农夫和狼到B（A有羊 B有白菜和狼）
之后农夫在去一趟A把羊带上 到B就可以了

简单的说
首先 A狼和白菜------------------------B农夫和羊
农夫回去 A农夫、狼和白菜----------------B羊
农夫载白菜过河 A狼---------------------------------B农夫、羊和白菜
农夫再和羊一起渡回去 A农夫、狼和羊-------------------B白菜
农夫带狼过河 A羊---------------------------------B农夫、狼和白菜
农夫再次肚子回去 A农夫和羊-------------------------B狼和白菜
农夫最后带羊过河 A（无）----------------------------B农夫、狼、羊和白菜

Answer 2

#include
#include
#include

#define MAX_STEP 20

/*二维数组a的行下标表示次数，列下标分别表示: 0 - 狼，1－羊，2－菜，3－农夫，值表示：0－本岸，1－对岸
如：a[2][0]=1表示狼在第二次后在对岸*/
int a[MAX_STEP][4]; //初始状态都未赋值,默认为0， 意思是4个都在本岸
int b[MAX_STEP]; //数组b是用来存放每一步操作的动作对象，如b[0]=1,那么就表示第一步农民“带羊”（name[b[0]+1]即name[2]），这个说明只是打个比方

char *name[] =
{
"空手",
"带狼",
"带羊",
"带菜"
};

void search(int iStep)
{
int i;
if (a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4)
//递归的结束条件，最后的结果，即4个都到对岸后，分别输入每一步的操作
{
for (i = 0; i < iStep; i++)
{
if (a[i][3] == 0) //a[i][3]表示农夫，因为每次农夫必须动，所以根据农夫的位置来判断本次的行动，也就是农夫在本岸的话动作应该是带XX到对岸
{
printf("%s到对岸\n", name[b[i] + 1]);
}
else //否则相反
{
printf("%s回本岸\n", name[b[i] + 1]);
}
}
printf("\n");
return;
}
//下面这个for语句是一个比较的语句，处理的问题是，当第n步移动后，如果跟前面某一步移动后的状态时一样的，那么表示没有意义，结束本次递归，防止进入死循环
for (i = 0; i < iStep; i++)
{
if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0)
{
return;
}
}
//下面这个if表示当本次是这种情况：农夫和羊没在一起，而且羊和狼在一起或者羊和菜在一起，那么就会违反规则，则结束本次调用
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; //将第istep步骤的操作赋值给b[istep],默认为-1,即最后输出的时候是name[b[i] + 1]表示空手
memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1])); //一维数组的复制,将二维数组上一行赋值给下一行
a[iStep + 1][3] = 1 - a[iStep + 1][3]; //由于0表示本岸，1表示对岸，1-值表示交换，即每次农夫是必须动的。
if (i == -1)
//如果i==-1就递归下一次，这里表示只有农夫运动
{
search(iStep + 1);
}
else if (a[iStep][i] == a[iStep][3])
//从0到2表示 0 - 狼，1－羊，2－菜，判断是否跟农夫在一边，在一边才可能被带走
{
a[iStep + 1][i] = a[iStep + 1][3]; //表示i被带走了，那么下一次的值因为是跟农夫一样的
search(iStep + 1);
}
}
}

int main()
{
search(0);
return 0;
}

/*大体思路是：用递归的方法，一个结束条件是4个都到对岸，二个递归中断条件是1)本次移动后，跟之前的某一次状态一样，那么重复，没意义，中断；2)本次
移动后，违反了规则，羊或者菜被吃了，中断本次调用。其他则进入下一次迭代。*/

Answer 3

南岸 小船 北岸
0 农夫 狼 羊 白菜
1 狼 白菜 农夫 羊
2狼 白菜 农夫 羊
3狼 白菜 农夫 羊
4狼 农夫 羊 白菜
5羊 狼 农夫 白菜
6羊 农夫 狼 白菜
7 农夫 羊
8 农夫 羊狼 白菜

Answer 4

方案：农夫先把羊运过河，第二次再把菜运过河，此时又把羊捎回，第三次放下羊，同时把豺狗
运过河，第四次把羊运过河．

Answer 5

怎么过我是知道但是你说的好复杂 貌似不是怎么过的问题......