C++ 农夫过河问题解决方案 - 深度优先搜索

以下是一个用 C++ 编写的农夫过河问题解决方案，使用深度优先搜索算法：

#include <iostream>
#include <vector>

using namespace std;

// 表示东岸和西岸的状态
struct State {
    bool farmer;  // 表示农夫是否在岸上
    bool wolf;    // 表示狼是否在岸上
    bool sheep;   // 表示羊是否在岸上
    bool cabbage; // 表示白菜是否在岸上
};

// 判断当前状态是否合法
bool isValidState(const State& state) {
    // 如果农夫不在场，则狼吃羊或者羊吃白菜，返回false
    if (!state.farmer && ((state.wolf && state.sheep) || (state.sheep && state.cabbage))) {
        return false;
    }
    // 如果农夫在场，则狼吃羊或者羊吃白菜，返回false
    if (state.farmer && ((state.wolf && !state.sheep) || (state.sheep && !state.cabbage))) {
        return false;
    }
    return true;
}

// 判断两个状态是否相同
bool isSameState(const State& state1, const State& state2) {
    return state1.farmer == state2.farmer && state1.wolf == state2.wolf && state1.sheep == state2.sheep && state1.cabbage == state2.cabbage;
}

// 判断当前状态是否已经访问过
bool isVisited(const State& state, const vector<State>& visitedStates) {
    for (const auto& visitedState : visitedStates) {
        if (isSameState(state, visitedState)) {
            return true;
        }
    }
    return false;
}

// 深度优先搜索
bool dfs(const State& currentState, const State& targetState, vector<State>& visitedStates) {
    // 如果当前状态与目标状态相同，则找到了解决方案
    if (isSameState(currentState, targetState)) {
        visitedStates.push_back(targetState);
        return true;
    }

    // 尝试移动每一样物品
    vector<State> possibleStates;
    State newState;

    // 将农夫移动到对岸
    newState = currentState;
    newState.farmer = !newState.farmer;
    if (isValidState(newState) && !isVisited(newState, visitedStates)) {
        possibleStates.push_back(newState);
    }

    // 将农夫与狼一起移动到对岸
    newState = currentState;
    newState.farmer = !newState.farmer;
    newState.wolf = !newState.wolf;
    if (isValidState(newState) && !isVisited(newState, visitedStates)) {
        possibleStates.push_back(newState);
    }

    // 将农夫与羊一起移动到对岸
    newState = currentState;
    newState.farmer = !newState.farmer;
    newState.sheep = !newState.sheep;
    if (isValidState(newState) && !isVisited(newState, visitedStates)) {
        possibleStates.push_back(newState);
    }

    // 将农夫与白菜一起移动到对岸
    newState = currentState;
    newState.farmer = !newState.farmer;
    newState.cabbage = !newState.cabbage;
    if (isValidState(newState) && !isVisited(newState, visitedStates)) {
        possibleStates.push_back(newState);
    }

    // 对每一个可能的状态进行递归搜索
    for (const auto& possibleState : possibleStates) {
        visitedStates.push_back(possibleState);
        if (dfs(possibleState, targetState, visitedStates)) {
            return true;
        }
        visitedStates.pop_back();
    }

    return false;
}

int main() {
    // 初始化初始状态和目标状态
    State initialState = {true, true, true, true};
    State targetState = {false, false, false, false};

    // 记录访问过的状态
    vector<State> visitedStates;
    visitedStates.push_back(initialState);

    // 开始深度优先搜索
    if (dfs(initialState, targetState, visitedStates)) {
        // 输出解决方案
        for (const auto& state : visitedStates) {
            cout << "农夫: " << (state.farmer ? "东岸" : "西岸") << ", ";
            cout << "狼: " << (state.wolf ? "东岸" : "西岸") << ", ";
            cout << "羊: " << (state.sheep ? "东岸" : "西岸") << ", ";
            cout << "白菜: " << (state.cabbage ? "东岸" : "西岸") << endl;
        }
    } else {
        cout << "无解" << endl;
    }

    return 0;
}

该程序使用深度优先搜索算法，通过尝试移动农夫和其他物品来搜索可能的状态。在搜索过程中，使用 isValidState 函数来判断当前状态是否合法，使用 isVisited 函数来判断当前状态是否已经访问过。最终找到的解决方案保存在 visitedStates 中，并输出到控制台上。如果找不到解决方案，则输出“无解”。