求解农夫过河问题的C++代码

好的，以下是求解农夫过河问题的C++代码，采用了广度优先搜索算法：

#include <iostream>
#include <queue>
#include <set>
using namespace std;

struct State {
    int wolf, goat, cabbage, farmer;
    bool operator==(const State& other) const {
        return wolf == other.wolf && goat == other.goat && cabbage == other.cabbage && farmer == other.farmer;
    }
    bool is_valid() const {
        if ((goat == cabbage && farmer != goat) || (wolf == goat && farmer != wolf)) {
            return false;
        }
        return true;
    }
};

struct Node {
    State state;
    Node* parent;
    Node(const State& s, Node* p) : state(s), parent(p) {}
};

void print_path(Node* node) {
    if (node->parent == nullptr) {
        cout << "初始状态：" << endl;
    } else {
        print_path(node->parent);
    }
    cout << "狼：" << node->state.wolf << "，羊：" << node->state.goat << "，菜：" << node->state.cabbage << "，农夫：" << node->state.farmer << endl;
}

void bfs() {
    queue<Node*> q;
    set<State> visited;
    State initial_state = {1, 1, 1, 1}; // 初始状态
    if (!initial_state.is_valid()) {
        cout << "初始状态不合法！" << endl;
        return;
    }
    Node* initial_node = new Node(initial_state, nullptr);
    q.push(initial_node);
    visited.insert(initial_state);
    while (!q.empty()) {
        Node* current_node = q.front();
        q.pop();
        State current_state = current_node->state;
        if (current_state.wolf == 0 && current_state.goat == 0 && current_state.cabbage == 0 && current_state.farmer == 0) {
            print_path(current_node);
            return;
        }
        int farmer = current_state.farmer == 1 ? 0 : 1;
        for (int wolf = 0; wolf <= 1; wolf++) {
            for (int goat = 0; goat <= 1; goat++) {
                for (int cabbage = 0; cabbage <= 1; cabbage++) {
                    State next_state = {wolf, goat, cabbage, farmer};
                    if (visited.count(next_state) || !next_state.is_valid()) {
                        continue;
                    }
                    visited.insert(next_state);
                    Node* next_node = new Node(next_state, current_node);
                    q.push(next_node);
                }
            }
        }
    }
    cout << "无解！" << endl;
}

int main() {
    bfs();
    return 0;
}

这个程序使用了一个State结构体来表示状态，其中wolf、goat、cabbage、farmer分别表示狼、羊、菜、农夫是否在当前岸边（1表示在，0表示不在）。is_valid函数用来判断当前状态是否合法。Node结构体表示搜索树中的一个节点，其中state表示节点对应的状态，parent表示节点的父节点。print_path函数用来输出从初始状态到当前状态的路径。bfs函数使用广度优先搜索算法来求解问题，找到符合条件的终止状态后，调用print_path函数输出路径。

需要注意的是，这个程序只是一个简单的示例，还有很多可以改进的地方。比如，可以添加一些启发式信息来加速搜索，或者使用A*算法来进行搜索。