农夫过河的c++代码

以下是一个简单的C++代码实现农夫过河问题的状态转换算法：

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

vector<int> vec; // 用于保存过河结果

void dfs(int wolf, int sheep, int cabbage, int farmer, int flag) {
    if (wolf == 1 && sheep == 1 && cabbage == 1) { // 如果所有物品都过河了，输出结果
        for (int i = 0; i < vec.size(); i++) {
            if (vec[i] == 1) cout << "羊 ";
            else if (vec[i] == -1) cout << "羊回 ";
            else if (vec[i] == 2) cout << "狼 ";
            else if (vec[i] == -2) cout << "狼回 ";
            else if (vec[i] == 3) cout << "菜 ";
            else if (vec[i] == -3) cout << "菜回 ";
            else if (vec[i] == 4) cout << "农夫 ";
            else if (vec[i] == -4) cout << "农夫回 ";
        }
        cout << endl;
        return;
    }
    if (flag == 1) { // 农夫在原岸
        if (wolf == 1 && sheep == 1) return; // 狼和羊不能单独在一起
        if (sheep == 1 && cabbage == 1) return; // 羊和菜不能单独在一起
        if (wolf == 1 && cabbage == 1) return; // 狼和菜不能单独在一起
        vec.push_back(farmer * 4); // 农夫过河
        if (wolf == 1) dfs(0, sheep, cabbage, -1 * farmer, 2); // 狼在原岸
        else dfs(1, sheep, cabbage, -1 * farmer, 2); // 狼在对岸
        vec.pop_back(); // 农夫返回
    }
    else { // 农夫在对岸
        vec.push_back(farmer * -4); // 农夫返回
        if (wolf == 1) dfs(0, sheep, cabbage, -1 * farmer, 1); // 狼在对岸
        else dfs(1, sheep, cabbage, -1 * farmer, 1); // 狼在原岸
        vec.pop_back(); // 农夫过河
    }
    if (flag == 2) { // 农夫在原岸
        if (wolf == 1) return; // 狼不能单独在一起
        vec.push_back(farmer * 4 + sheep * 1); // 农夫带羊过河
        if (wolf == 1) dfs(0, 0, cabbage, -1 * farmer, 2); // 狼在原岸
        else dfs(1, 0, cabbage, -1 * farmer, 2); // 狼在对岸
        vec.pop_back(); // 农夫带羊返回
        if (cabbage == 1) return; // 菜不能单独在一起
        vec.push_back(farmer * 4 + cabbage * 3); // 农夫带菜过河
        if (wolf == 1) dfs(0, sheep, 0, -1 * farmer, 2); // 狼在原岸
        else dfs(1, sheep, 0, -1 * farmer, 2); // 狼在对岸
        vec.pop_back(); // 农夫带菜返回
    }
    else { // 农夫在对岸
        if (wolf == 1) return; // 狼不能单独在一起
        vec.push_back(farmer * -4 + sheep * -1); // 农夫带羊返回
        if (wolf == 1) dfs(0, sheep, cabbage, -1 * farmer, 1); // 狼在对岸
        else dfs(1, sheep, cabbage, -1 * farmer, 1); // 狼在原岸
        vec.pop_back(); // 农夫带羊过河
        if (cabbage == 1) return; // 菜不能单独在一起
        vec.push_back(farmer * -4 + cabbage * -3); // 农夫带菜返回
        if (wolf == 1) dfs(0, sheep, cabbage, -1 * farmer, 1); // 狼在对岸
        else dfs(1, sheep, cabbage, -1 * farmer, 1); // 狼在原岸
        vec.pop_back(); // 农夫带菜过河
    }
}

int main() {
    dfs(1, 1, 1, 1, 1); // 初始状态，所有物品都在原岸
    return 0;
}