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

狼羊菜过河问题可以用深度优先搜索算法来解决。

首先，我们需要定义狼羊菜过河的状态。每个状态包括河的两岸以及船的位置，用一个数组来表示：state[0]、state[1]表示左岸的状态，state[2]、state[3]表示右岸的状态，state[4]表示船的位置，0表示船在左岸，1表示船在右岸。

接下来，我们需要定义可行的状态转移。每次可以将农夫和另外一种物品（狼、羊、菜）一起带过河，但是如果左岸有狼和羊或者羊和菜，则狼会吃掉羊，菜会被羊吃掉，所以这种状态是不可行的。

最后，我们使用深度优先搜索算法来搜索所有可行的状态，找到一种状态使得左岸和右岸的物品状态都为全1，则表示问题得到解决。

以下是狼羊菜过河问题的C语言算法代码实现：

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

int state[5]; // 状态数组

// 判断当前状态是否可行
int is_valid() {
    if (state[0] == 1 && state[2] == 1 && (state[1] == 1 || state[3] == 1)) // 狼吃羊
        return 0;
    if (state[0] == 1 && state[4] == 1 && (state[1] == 1 || state[3] == 1)) // 菜被羊吃掉
        return 0;
    if (state[2] == 1 && state[4] == 0 && (state[1] == 0 || state[3] == 0)) // 船必须要有人
        return 0;
    return 1;
}

// 深度优先搜索
void dfs() {
    if (state[0] == 1 && state[1] == 1 && state[2] == 1 && state[3] == 1) { // 左岸和右岸的状态都为全1，问题得到解决
        printf("found solution: wolf=%d, sheep=%d, vegetable=%d\n", state[0], state[1], state[2]);
        return;
    }
    for (int i = 0; i < 5; i++) { // 枚举每一种物品（包括农夫）
        if (state[i] == state[4]) { // 物品在船上
            state[i] = !state[i]; // 物品从船上下来
            if (is_valid()) { // 判断状态是否可行
                dfs(); // 继续搜索
            }
            state[i] = !state[i]; // 恢复状态
        }
    }
}

int main() {
    memset(state, 0, sizeof(state)); // 初始化状态数组
    dfs(); // 开始搜索
    return 0;
}