狼、羊、菜和农夫过河问题C++

以下是一个简单的 C++ 解法：

#include <iostream>
#include <vector>

using namespace std;

bool is_valid(vector<int>& state) {
    // 状态合法性判断函数，即判断是否有任意两个元素相等
    for (int i = 0; i < state.size(); i++) {
        for (int j = i+1; j < state.size(); j++) {
            if (state[i] == state[j]) {
                return false;
            }
        }
    }
    return true;
}

bool dfs(vector<int>& state, vector<vector<int>>& path) {
    if (state == vector<int>({3, 3, 1, 1})) {
        // 如果已经到达目标状态，则返回真
        return true;
    }

    // 状态合法性判断
    if (!is_valid(state)) {
        return false;
    }

    // 枚举每一个可能的动作
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (i == j) {
                continue;
            }

            vector<int> new_state = state;
            int farmer_pos = state[2];
            int wolf_pos = state[0];
            int goat_pos = state[1];
            int cabbage_pos = state[3];

            if (farmer_pos == wolf_pos && i != 2 && j != 2) {
                // 如果农夫和狼在同一岸，而且农夫没有带狼过河，则狼会吃羊
                continue;
            }

            if (farmer_pos == goat_pos && i == 3 && j == 2) {
                // 如果农夫和羊在同一岸，而且农夫没有带羊过河，则羊会被狼吃掉
                continue;
            }

            if (farmer_pos == cabbage_pos && i == 2 && j == 3) {
                // 如果农夫和菜在同一岸，而且农夫没有带菜过河，则菜会被羊吃掉
                continue;
            }

            new_state[2] = 1 - farmer_pos;  // 农夫过河
            new_state[i] = 1 - state[i];  // 第 i 个物品过河
            new_state[j] = 1 - state[j];  // 第 j 个物品过河

            path.push_back(new_state);  // 将新状态加入路径

            if (dfs(new_state, path)) {  // 递归求解
                return true;
            }

            path.pop_back();  // 回溯
        }
    }

    return false;
}

int main() {
    vector<int> initial_state({0, 0, 0, 0});
    vector<vector<int>> path({initial_state});

    dfs(initial_state, path);

    for (int i = 0; i < path.size(); i++) {
        cout << "Step " << i << ":" << endl;
        cout << "Wolf: " << (path[i][0] == 0 ? "L" : "R") << endl;
        cout << "Goat: " << (path[i][1] == 0 ? "L" : "R") << endl;
        cout << "Farmer: " << (path[i][2] == 0 ? "L" : "R") << endl;
        cout << "Cabbage: " << (path[i][3] == 0 ? "L" : "R") << endl;
        cout << endl;
    }

    return 0;
}

这里使用了深度优先搜索（DFS）算法来求解问题，具体思路是：从初始状态开始，依次枚举所有可能的动作，然后递归地求解下一个状态，直到找到目标状态或者无法继续搜索为止。在搜索过程中，需要判断当前状态的合法性，即判断是否有任意两个元素相等，以及判断狼、羊和菜是否会发生冲突。如果找到了目标状态，就将路径保存下来，并返回真；否则返回假。为了方便回溯，我们需要在搜索过程中记录下路径。