羊、狼、农夫过河C语言

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

同狼羊菜过河问题，我们需要定义状态数组，表示羊、狼、农夫和船的位置。每次可以将农夫和一种物品（羊或狼）一起带过河，但是如果左岸有羊和狼，则狼会吃掉羊，所以这种状态是不可行的。

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

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

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

// 判断当前状态是否可行
int is_valid() {
    if (state[0] == 1 && state[1] == 1 && state[2] == 0) // 狼吃羊
        return 0;
    return 1;
}

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

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