狼、羊、菜和农夫过河问题C++

以下是一个简单的C++实现，用于解决狼、羊、菜和农夫过河问题：

#include <iostream>
#include <cstring>
using namespace std;

bool is_valid_state(int wolf, int goat, int cabbage) {
    // 判断当前状态是否合法
    if ((goat == cabbage) && (wolf != goat)) return false;
    if ((wolf == goat) && (goat != cabbage)) return false;
    return true;
}

void dfs(int wolf, int goat, int cabbage, int farmer, int depth, char path[]) {
    if (depth == 8) {
        path[depth] = '\0';
        cout << path << endl;  // 打印路径
        return;
    }
    // 农夫从左岸到右岸
    if (farmer == 0) {
        if (is_valid_state(wolf, goat, cabbage + 1)) {
            path[depth] = 'C';
            dfs(wolf, goat, cabbage + 1, 1, depth + 1, path);
        }
        if (is_valid_state(wolf, goat + 1, cabbage)) {
            path[depth] = 'G';
            dfs(wolf, goat + 1, cabbage, 1, depth + 1, path);
        }
        if (is_valid_state(wolf + 1, goat, cabbage)) {
            path[depth] = 'W';
            dfs(wolf + 1, goat, cabbage, 1, depth + 1, path);
        }
    }
    // 农夫从右岸到左岸
    else {
        if (is_valid_state(wolf, goat, cabbage - 1)) {
            path[depth] = 'c';
            dfs(wolf, goat, cabbage - 1, 0, depth + 1, path);
        }
        if (is_valid_state(wolf, goat - 1, cabbage)) {
            path[depth] = 'g';
            dfs(wolf, goat - 1, cabbage, 0, depth + 1, path);
        }
        if (is_valid_state(wolf - 1, goat, cabbage)) {
            path[depth] = 'w';
            dfs(wolf - 1, goat, cabbage, 0, depth + 1, path);
        }
    }
}

int main() {
    int wolf = 1, goat = 1, cabbage = 1, farmer = 0;
    char path[9];  // 存储路径
    dfs(wolf, goat, cabbage, farmer, 0, path);
    return 0;
}

在上面的实现中，我们使用深度优先搜索算法（DFS）来穷举所有可能的状态，并使用 `is_valid_state()` 函数来判断当前状态是否合法。一旦找到一条可行路径，就会打印出该路径。