c++解决农夫过河问题代码

以下是使用 C++ 语言实现的农夫过河问题的代码：

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

bool is_valid(const vector<int>& state) {
    /* 判断状态是否合法 */
    if (state[1] == state[2] && state[0] != state[1]) {
        return false;
    }
    if (state[0] == state[1] && state[0] != state[2]) {
        return false;
    }
    return true;
}

vector<int> move(const vector<int>& state, int item) {
    /* 将物品移动到另一边 */
    vector<int> new_state = state;
    new_state[0] = 1 - new_state[0];  // 将船移动到另一边
    new_state[item] = 1 - new_state[item];  // 将物品移动到另一边
    return new_state;
}

bool dfs(const vector<int>& state, vector<pair<int, int>>& path, unordered_set<vector<int>>& visited) {
    /* 使用深度优先搜索求解问题 */
    if (state == vector<int>({1, 1, 1})) {  // 找到了一组解
        for (auto p : path) {
            cout << "将物品 " << p.first << " 移动到 " << (p.second == 0 ? "原岸" : "对岸") << endl;
        }
        return true;
    }
    visited.insert(state);
    for (int i = 0; i < 3; i++) {
        if (state[i] == state[0]) {  // 物品在同一边
            vector<int> new_state = move(state, i);
            if (is_valid(new_state) && visited.find(new_state) == visited.end()) {
                path.push_back(make_pair(i, state[0]));
                if (dfs(new_state, path, visited)) {
                    return true;
                }
                path.pop_back();
            }
        }
    }
    return false;
}

int main() {
    dfs(vector<int>({0, 0, 0}), vector<pair<int, int>>(), unordered_set<vector<int>>());
    return 0;
}

该代码与前面的 Python 代码类似，使用深度优先搜索算法实现，其中 `is_valid` 函数用于判断状态是否合法，`move` 函数用于将物品移动到另一边，`dfs` 函数用于使用深度优先搜索算法求解问题。具体而言，`dfs` 函数首先判断当前状态是否是目标状态，如果是则输出路径并返回 `true`，否则遍历每个物品，如果该物品和农夫在同一边，则将该物品移动到对岸，然后判断新状态是否合法并且是否已经被访问过，如果是则递归搜索该状态。注意，为了方便输出解，我们使用了一个 `path` 变量来记录路径，其中每个元素表示将某个物品移动到原岸或对岸。