c语言递归解决人羊狼草过河问题并且打印出运送过程

人羊狼草过河问题（也称为狼、羊和菜问题）是一个经典的逻辑谜题。在这个问题中，有一条河和一只船，需要将人、羊、狼和菜运送到河的对岸，但船只能容纳人和另外一个对象。问题的挑战在于，在人不在场的情况下，羊不能和狼单独留在一起，否则羊会被狼吃掉；同样，菜也不能和羊单独留在一起，否则羊会吃掉菜。

递归解法通过不断尝试将不同的组合运送到对岸，并在每次移动后检查是否有违例情况发生。下面是一个简化版的C语言递归解决这个问题的示例代码，以及打印出整个运送过程：

#include <stdio.h>

// 定义状态结构体
typedef struct {
    int man;    // 人所在的位置
    int sheep;  // 羊所在的位置
    int wolf;   // 狼所在的位置
    int cabbage;// 菜所在的位置
} State;

// 打印当前状态
void printState(State s) {
    printf("人：%s, 羊：%s, 狼：%s, 菜：%s\n",
           s.man == 1 ? "河对岸" : "河边",
           s.sheep == 1 ? "河对岸" : "河边",
           s.wolf == 1 ? "河对岸" : "河边",
           s.cabbage == 1 ? "河对岸" : "河边");
}

// 检查是否为安全状态
int isSafe(State s) {
    if ((s.sheep == 1 && s.wolf == 1) || (s.sheep == s.cabbage && s.sheep != s.man)) {
        return 0; // 狼和羊或羊和菜单独在一起，且人不在，不安全
    }
    return 1;
}

// 递归函数
int crossRiver(State s, int step) {
    if (s.man == 0 && s.sheep == 0 && s.wolf == 0 && s.cabbage == 0) {
        printf("第%d步：所有都安全地到达了对岸。\n", step);
        return 1; // 所有都成功过河
    }

    // 人带着羊过河
    if (s.man == 1 && s.sheep == 1) {
        s.man = s.sheep = 0; // 人和羊回到河边
        if (isSafe(s)) {
            printState(s);
            if (crossRiver(s, step + 1)) return 1;
            s.man = s.sheep = 1; // 回溯
        }
    }
    // 人带着狼过河
    else if (s.man == 1 && s.wolf == 1) {
        s.man = s.wolf = 0; // 人和狼回到河边
        if (isSafe(s)) {
            printState(s);
            if (crossRiver(s, step + 1)) return 1;
            s.man = s.wolf = 1; // 回溯
        }
    }
    // 人带着菜过河
    else if (s.man == 1 && s.cabbage == 1) {
        s.man = s.cabbage = 0; // 人和菜回到河边
        if (isSafe(s)) {
            printState(s);
            if (crossRiver(s, step + 1)) return 1;
            s.man = s.cabbage = 1; // 回溯
        }
    }
    // 人单独过河
    else if (s.man == 1) {
        s.man = 0; // 人回到河边
        if (isSafe(s)) {
            printState(s);
            if (crossRiver(s, step + 1)) return 1;
            s.man = 1; // 回溯
        }
    }
    return 0;
}

int main() {
    State start = {1, 1, 1, 1}; // 初始状态，所有都在河边
    if (!crossRiver(start, 1)) {
        printf("没有解决方案。\n");
    }
    return 0;
}

请注意，上面的代码是一个简化版的递归解决方案，它并没有穷举所有可能的移动组合，而是简单地展示了如何使用递归来解决这个问题。在实际应用中，可能需要更复杂的逻辑来确保找到所有可能的解决方案。