农夫过河数据结构代码

这里提供一种可能的农夫过河问题的数据结构代码实现：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 定义一个结构体表示农夫、狼、羊和白菜
struct State {
    int farmer; // 农夫所在岸边，0表示南岸，1表示北岸
    int wolf; // 狼所在岸边，0表示南岸，1表示北岸
    int goat; // 羊所在岸边，0表示南岸，1表示北岸
    int cabbage; // 白菜所在岸边，0表示南岸，1表示北岸
};

// 判断当前状态是否安全
bool isSafe(const State& state) {
    // 如果羊和白菜在同一岸边，且农夫不在，返回false
    if (state.goat == state.cabbage && state.farmer != state.goat) {
        return false;
    }
    // 如果狼和羊在同一岸边，且农夫不在，返回false
    if (state.wolf == state.goat && state.farmer != state.wolf) {
        return false;
    }
    // 否则返回true
    return true;
}

// 定义一个结构体表示路径上的一步
struct Step {
    State state; // 当前状态
    string action; // 农夫的动作，如"带羊过河"
};

// 定义一个结构体表示路径
struct Path {
    vector<Step> steps; // 路径上的所有步骤
};

// 递归求解农夫过河问题
void solve(const State& state, Path& path, vector<Path>& paths) {
    // 如果当前状态是终止状态，将路径加入结果集
    if (state.farmer == 1 && state.wolf == 1 && state.goat == 1 && state.cabbage == 1) {
        paths.push_back(path);
        return;
    }
    // 枚举所有可能的下一步状态
    for (int i = 0; i < 4; i++) {
        State next = state;
        // 农夫带着物品过河
        if (i == 0) {
            if (next.farmer == next.wolf) {
                continue; // 狼和农夫不在同一岸边，不能带狼过河
            }
            next.farmer = 1 - next.farmer;
            next.goat = 1 - next.goat;
            path.steps.push_back({next, "带羊过河"});
            if (isSafe(next)) {
                solve(next, path, paths);
            }
            path.steps.pop_back();
            next.farmer = 1 - next.farmer;
            next.goat = 1 - next.goat;
        } else if (i == 1) {
            if (next.farmer == next.goat) {
                continue; // 羊和农夫不在同一岸边，不能带羊过河
            }
            next.farmer = 1 - next.farmer;
            next.wolf = 1 - next.wolf;
            path.steps.push_back({next, "带狼过河"});
            if (isSafe(next)) {
                solve(next, path, paths);
            }
            path.steps.pop_back();
            next.farmer = 1 - next.farmer;
            next.wolf = 1 - next.wolf;
        } else if (i == 2) {
            if (next.farmer == next.cabbage) {
                continue; // 白菜和农夫不在同一岸边，不能带白菜过河
            }
            next.farmer = 1 - next.farmer;
            next.goat = 1 - next.goat;
            path.steps.push_back({next, "带羊过河"});
            if (isSafe(next)) {
                solve(next, path, paths);
            }
            path.steps.pop_back();
            next.farmer = 1 - next.farmer;
            next.goat = 1 - next.goat;
        } else {
            next.farmer = 1 - next.farmer;
            path.steps.push_back({next, "独自过河"});
            if (isSafe(next)) {
                solve(next, path, paths);
            }
            path.steps.pop_back();
            next.farmer = 1 - next.farmer;
        }
    }
}

int main() {
    State initial = {0, 0, 0, 0}; // 初始状态
    Path path; // 当前路径
    vector<Path> paths; // 结果集
    solve(initial, path, paths);
    // 输出所有解
    for (const auto& p : paths) {
        cout << "方案：" << endl;
        for (const auto& s : p.steps) {
            cout << s.action << endl;
        }
        cout << endl;
    }
    return 0;
}