Question

农夫过河问题。急急急

#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;
}
能给我详细解释一下这段程序运用了哪些基本源代码及其基本功能么？非常感谢啊，拜托了

Answer 1

程序就是求解农夫过河问题：
农夫带着一狼，一羊和一些菜过河。河边只有一船，一次农夫只能带一样东西。无人时，狼要吃羊，羊要吃菜，程序将找出所有农夫过河的方案。

首先要表示狼，羊，菜和农夫所在的位置，4者的位置有本岸和对岸两种情况，分别用0和1表示，4者，所以用一个有4元素的数组。为了要记录每一步，程序中使用了一个二维数组a[MAX_STEP][4]，记录每一步4者所在位置。第一步就是a[0]，第二布是a[1]...而，a[0][0]就表示第一步狼在本岸(0)还是对岸(1)，a[0][1]表示第一步羊在本岸还是对岸......
为了记录每一次农夫过河时的状态，使用了一个数组b[MAX_STEP]，数组中的元素的值可能为-1, 0, 1, 2，分别表示农夫在过河时，是空手，带狼，带羊，带菜。

第一步的状态是狼，羊，菜和农夫都在本案，所以a[0][0]到a[0][3]都是0，本来应该初始化一下，但a是全局变量，所以自动初始化为0，所以程序中省下了这一步。
search是一个递归函数，通过不断的查找可能的下一步，找出一个方案，是一种深度优先搜索。
a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4意味着第 iStep时，a[iStep][0]到a[iStep][3]都为1，表示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]);
}
}
输出每一步
a[i][3]是农夫在本岸还是对岸，如果为0，在本岸，下一步肯定是到对岸，所以打印"...到对岸"，而name[b[i]+1]找出对应带的东西的描述。
for (i = 0; i < iStep; i++)
{
if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0)
{
return;
}
}
判定是否会死循环，如果当前状态在以前出现过，那么就会出现死循环。用当前这步的状态a[iStep]和以前的所有步a[i] (i=0; i <iStep; i++)比较。memcmp是内存比较函数，可以用于比较数组，返回值为0，表示数组中所有值相同。
如果相同，就直接返回，不再查找。

if (a[iStep][1] != a[iStep][3] && (a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1]))
{
return;
}

判定羊会吃菜，或狼会吃羊的情况。
当农夫和羊在一起的时候，狼不会吃羊，羊也不会吃菜，所以只有当农夫和羊不在一起(a[iStep][1] != a[iStep][3])时，才可能发生“吃”的状态。
而且“吃”的情况必须是在菜和羊在一起(a[iStep][2] == a[iStep][1])或者羊和狼在一起(a[iStep][0] == a[iStep][1])
发生吃的情况是，返回，不再查找。

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);
}
}
但现在，已经确保了上一步是“安全”的，可以继续查找。
-1, 0, 1, 2分别表示渡河时4种情况，空手，带狼，带羊，带菜。
memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1])); 复制当前步的数组到下一步。
农夫的状态肯定会发生改变，所以a[iStep + 1][3] = 1 - a[iStep + 1][3]; 因为当a为0或1时，a = 1 - a会使a在0和1之间切换。
如果i== -1，表示空手，狼，羊，菜的状态都不会发生改变，所以直接搜索下一步(search(iStep + 1); )
否则要被带过去的东西(0, 1, 2分别表示0, 1, 2)的状态需要改变。
要带的东西必须和农夫同在本案或对岸(a[iStep][i] == a[iStep][3])，才可能带得了。只有在这种情况下，使要带的东西的状态和农夫相同(a[iStep + 1][i] = a[iStep + 1][3];)，并开始下一步的搜索(search(iStep + 1))。