关于数据结构:数据结构与算法经典题农夫过河问题讲解

题目：
一个农夫在河边带了一只狼、一只羊和一颗白菜，他须要把这三样货色用船带到河的对岸。然而，这艘船只能容下农夫自己和另外一样货色。如果农夫不在场的话，狼会吃掉羊，羊也会吃掉白菜。请编程为农夫解决这个过河问题。

思路：

看到这道题目，咱们先缕清这几样货色（包含一个人)他们之间的关系。在这道题里，咱们只能两两组合。其中，有几个限度条件
1. 狼不能和羊在一起
2. 羊不能和白菜在一起
（这两个条件也会成为咱们之后算法里逻辑做限度的一部分）

命名相干变量
当初，咱们对它们进行命名，咱们先用数字示意这些货色（和人）
0——狼、1——羊、2——白菜、3——农夫
（记得肯定是从 0 开始标记哦）

接下来，咱们就是标记河的两岸，咱们给河的两岸别离示意为东岸和西岸（当然北岸和南岸也行，随便啦）。以此证实他们达到，为了让咱们的计算机可能看懂，咱们示意为
0——起始河岸
1——达到的河岸

如果狼达到了对岸，咱们用数组就能够示意为 aStep 1，其余同理。
（这里的 a 数组示意存储每一步中各个对象所处的地位，除此之外，咱们还须要数组 b[N]来存储每一步中农夫是如何过河的）

因而，残缺代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 15
int a[N][4];
int b[N];
char* name[] =
{"","and wolf","and goat","and cabbage"};
int search(int step)
{
    int i;
    if (a[step][0] + a[step][1] + a[step][2] + a[step][3] = 4)
    {for (i = 0; i <= step; i++)
        {printf("east;");
            if (a[i][0] == 0)
                printf("wolf");
            if (a[i][1] == 0)
                printf("goat");
            if (a[i][2] == 0)
                printf("cabbage");
            if (a[i][3] == 0)
                printf("farmer");
            if (a[i][0] && a[i][1] && a[i][2] && a[i][3])
                printf("none");
            printf(" ");
            printf("west;");
            if (a[i][0] == 1)
                printf("wolf");
            if (a[i][1] == 1)
                printf("goat");
            if (a[i][2] == 1)
                printf("cabbage");
            if (a[i][3] == 1)
                printf("farmer");
            if (!(a[i][0] || a[i][1] || a[i][2] || a[i][3]))
                printf("none");
            printf("\n\n\n");
            if (i < Step)
                printf("the %d time\n", i + 1);
            if (i > 0 && i < Step)
            {if (a[i][3] == 0)  /* 农夫在本岸 */
                {printf("----->  farmer");
                    printf("%s\n", name[b[i] + 1]);
                }
                else      /* 农夫在对岸 */
                {printf("<-----  farmer");
                    printf("%s\n", name[b[i] + 1]);
                }
            }
        }
        printf("\n\n\n\n");
        return 0;
    }
    for (i = 0; i < Step; i++)
    {if (memcmp(a[i], a[Step], 16) == 0)  /* 若该步与以前步骤雷同，勾销操作 */
        {return 0;}
    }
    /* 若羊和农夫不在一块而狼和羊或者羊和白菜在一块，则勾销操作 */
    if (a[Step][1] != a[Step][3] && (a[Step][2] == a[Step][1] || a[Step][0] == a[Step][1]))
    {return 0;}
    /* 递归，从带第一种动物开始顺次向下循环，同时限定递归的界线 */
    for (i = -1; i <= 2; i++)
    {b[Step] = i;
        memcpy(a[Step + 1], a[Step], 16);  /* 复制上一步状态，进行下一步挪动 */
        a[Step + 1][3] = 1 - a[Step + 1][3];  /* 农夫过来或者回来 */
        if (i == -1)
        {search(Step + 1);  /* 进行第一步 */
        }
        else
            if (a[Step][i] == a[Step][3])  /* 若该物与农夫同岸，带回 */
            {a[Step + 1][i] = a[Step + 1][3];  /* 带回该物 */
                search(Step + 1);  /* 进行下一步 */
            }
    }
    return 0;
}

int main()
{printf("\n\n             农夫过河问题，解决方案如下：\n\n\n");
    search(0);
    return 0;



}