狼羊菜过河问题c语言算法,算法系列之十四：狼、羊、菜和农夫过河问题

狼羊菜过河问题是经典的算法问题，可以使用深度优先搜索算法来解决。下面是C语言的实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100

int visited[MAX][MAX][MAX][MAX];
int wolf, sheep, cabbage, farmer;
int goal_wolf, goal_sheep, goal_cabbage, goal_farmer;

int is_valid(int wolf, int sheep, int cabbage, int farmer) {
    if ((wolf != sheep) && (sheep == cabbage)) return 0;
    if ((sheep != cabbage) && (wolf == sheep)) return 0;
    if ((wolf == goal_wolf) && (sheep == goal_sheep) && (cabbage == goal_cabbage) && (farmer == goal_farmer)) return 1;
    return 0;
}

void dfs(int wolf, int sheep, int cabbage, int farmer) {
    if (is_valid(wolf, sheep, cabbage, farmer)) {
        printf("Wolf: %d, Sheep: %d, Cabbage: %d, Farmer: %d\n", wolf, sheep, cabbage, farmer);
        return;
    }
    if (visited[wolf][sheep][cabbage][farmer]) return;
    visited[wolf][sheep][cabbage][farmer] = 1;
    if (farmer == 0) {
        dfs(wolf, sheep, cabbage, 1);
        if (wolf == farmer)
            dfs(wolf, sheep, cabbage, 1);
        if (sheep == farmer)
            dfs(wolf, sheep, cabbage, 1);
        if (cabbage == farmer)
            dfs(wolf, sheep, cabbage, 1);
    } else {
        if (wolf == farmer)
            dfs(wolf, sheep, cabbage, 0);
        if (sheep == farmer)
            dfs(wolf, sheep, cabbage, 0);
        if (cabbage == farmer)
            dfs(wolf, sheep, cabbage, 0);
        dfs(wolf, sheep, cabbage, 0);
    }
}

int main() {
    memset(visited, 0, sizeof(visited));
    wolf = 1, sheep = 1, cabbage = 1, farmer = 1;
    goal_wolf = 0, goal_sheep = 0, goal_cabbage = 0, goal_farmer = 0;
    dfs(wolf, sheep, cabbage, farmer);
    return 0;
}

在这个实现中，我们使用一个四维数组`visited`来记录访问过的状态，防止重复访问。`is_valid()`函数用于判断当前状态是否合法，`dfs()`函数用于进行深度优先搜索。在`main()`函数中，我们初始化起始状态和目标状态，然后调用`dfs()`函数开始搜索。