东航直飞日本哪些城市:农夫过河

运行结果如下：
带羊到对岸
空手回本岸
带狼到对岸
带羊回本岸
带菜到对岸
空手回本岸
带羊到对岸

带羊到对岸
空手回本岸
带菜到对岸
带羊回本岸
带狼到对岸
空手回本岸
带羊到对岸

以上是找出的所有解，共有两个解。

程序如下：
#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;
}

1.将羊带过河，独自回来
2.将狼带过河，把羊带回来
3.将草带过河，独自回来
4.将羊带过河

狼要咬羊，羊要吃草。所以，关键是要在渡河的任何一个步骤中，把羊和狼，羊和草分开，才能免受损失。
农夫可以先带羊到对岸，然后空手回来。第二步，带狼到对岸，但把兔子带回来。第三步，把羊留下，带草到对岸，空手回来。最后，带羊到对岸。这样三件东西都带过河去了，一件也没有遭受损失。

农夫带羊过去
农夫回来
农夫带狼过去
农夫带羊回来
农夫带草过去
农夫独自回来
农夫带羊过去