农夫过河问题c++代码

农夫过河问题是一个经典的逻辑问题，可以用来演示搜索算法和状态空间的应用。以下是一个简单的C++代码示例，用于解决农夫过河问题：

#include <iostream>
#include <queue>
#include <set>
#include <string>

using namespace std;

// 定义状态结构体
struct State {
    int farmer;  // 农夫的位置，0表示在起点，1表示在终点
    int wolf;    // 狼的位置，0表示在起点，1表示在终点
    int goat;    // 山羊的位置，0表示在起点，1表示在终点
    int cabbage; // 卷心菜的位置，0表示在起点，1表示在终点

    // 重载==运算符，用于判断两个状态是否相等
    bool operator==(const State& other) const {
        return farmer == other.farmer && wolf == other.wolf && goat == other.goat && cabbage == other.cabbage;
    }

    // 重载<运算符，用于在set容器中进行排序
    bool operator<(const State& other) const {
        if (farmer != other.farmer) return farmer < other.farmer;
        if (wolf != other.wolf) return wolf < other.wolf;
        if (goat != other.goat) return goat < other.goat;
        return cabbage < other.cabbage;
    }
};

// 判断当前状态是否合法
bool isValidState(const State& state) {
    // 如果山羊和狼在同一边，而农夫不在，或者山羊和卷心菜在同一边，而农夫不在，返回false
    if ((state.goat == state.wolf && state.farmer != state.goat) || (state.goat == state.cabbage && state.farmer != state.goat)) {
        return false;
    }
    return true;
}

// 判断当前状态是否为目标状态
bool isGoalState(const State& state) {
    // 所有物品都在终点时，返回true
    return state.farmer == 1 && state.wolf == 1 && state.goat == 1 && state.cabbage == 1;
}

// 农夫过河问题的求解函数
void solve() {
    queue<State> states;       // 存储待搜索的状态
    set<State> visitedStates;  // 存储已访问过的状态

    // 初始状态，农夫、狼、山羊、卷心菜都在起点
    State initialState = {0, 0, 0, 0};
    states.push(initialState);
    visitedStates.insert(initialState);

    while (!states.empty()) {
        State currentState = states.front();
        states.pop();

        // 判断当前状态是否为目标状态
        if (isGoalState(currentState)) {
            cout << "找到解答：" << endl;
            cout << "农夫\t狼\t山羊\t卷心菜" << endl;
            cout << (currentState.farmer == 0 ? "起点" : "终点") << "\t" << (currentState.wolf == 0 ? "起点" : "终点") << "\t"
                 << (currentState.goat == 0 ? "起点" : "终点") << "\t" << (currentState.cabbage == 0 ? "起点" : "终点") << endl;
            break;
        }

        // 生成下一步可能的状态
        for (int i = 0; i < 4; i++) {
            State nextState = currentState;

            // 农夫移动
            nextState.farmer = 1 - currentState.farmer;

            // 根据当前移动的物品，更新对应的位置
            switch (i) {
                case 0:  // 农夫独自过河
                    break;
                case 1:  // 农夫带狼过河
                    nextState.wolf = 1 - currentState.wolf;
                    break;
                case 2:  // 农夫带山羊过河
                    nextState.goat = 1 - currentState.goat;
                    break;
                case 3:  // 农夫带卷心菜过河
                    nextState.cabbage = 1 - currentState.cabbage;
                    break;
            }

            // 判断下一步状态是否合法且未访问过
            if (isValidState(nextState) && visitedStates.find(nextState) == visitedStates.end()) {
                states.push(nextState);
                visitedStates.insert(nextState);
            }
        }
    }

    if (states.empty()) {
        cout << "未找到解答！" << endl;
    }
}

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

这段代码使用了广度优先搜索算法来解决农夫过河问题。它通过遍历所有可能的状态，并判断状态是否合法和是否为目标状态来找到解答。在搜索过程中，使用队列来存储待搜索的状态，使用集合来存储已访问过的状态，以避免重复搜索。最终找到解答时，输出每个状态下农夫、狼、山羊、卷心菜的位置。