农夫过河问题c语言代码

以下是农夫过河问题的C语言代码实现：

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

#define FARMER 0
#define WOLF 1
#define SHEEP 2
#define CABBAGE 3

int state[4] = {0, 0, 0, 0}; // 初始状态，0表示在左岸，1表示在右岸
int goal[4] = {1, 1, 1, 1}; // 目标状态，全部在右岸

int is_valid(int *s) // 判断状态是否合法
{
    if (s[WOLF] == s[SHEEP] && s[FARMER] != s[WOLF]) // 狼吃羊
        return 0;
    if (s[SHEEP] == s[CABBAGE] && s[FARMER] != s[SHEEP]) // 羊吃白菜
        return 0;
    return 1;
}

int is_goal(int *s) // 判断是否到达目标状态
{
    for (int i = 0; i < 4; i++)
    {
        if (s[i] != goal[i])
            return 0;    }
    return 1;
}

void print_state(int *s) // 打印状态
{
    printf("farmer: %d, wolf: %d, sheep: %d, cabbage: %d\n", s[FARMER], s[WOLF], s[SHEEP], s[CABBAGE]);
}

void dfs(int *s) // 深度优先搜索
{
    if (is_goal(s))
    {
        print_state(s);
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        if (s[i] == s[FARMER]) // 物品在农夫这一侧
        {
            s[i] = !s[i]; // 农夫带着物品过河
            if (is_valid(s))
                dfs(s);
            s[i] = !s[i]; // 农夫带着物品回来
        }
    }
}

int main()
{
    dfs(state);
    return 0;
}