农夫过河问题 c++

农夫过河问题是经典的计算机科学算法问题，通常涉及一位农夫和他的动物（比如马、牛、羊）一起过河，但只有一条船。农夫每次只能携带他自己或者一只动物过河，而且有些动物在一起时不能同时上船，例如马和羊不能单独留在一起，因为马会吃掉羊。你需要设计一种策略，帮助农夫安全地将所有动物都带到对岸。

在 C++ 中，你可以通过递归回溯的方式来解决这个问题，使用数组或枚举类型来表示每一步的状态，并记录下已经过河的动物。以下是一个简化版的伪代码：

enum {农民, 马, 羊, 牛}; // 动物类型
bool dp[4][4]; // 动物组合是否可行

void dfs(int cur, int dest, vector<int>& animals) {
    if (cur == dest) return; // 所有动物都已经到达对岸
    for (int i = 0; i < 4; ++i) {
        if (!dp[cur][i] || (animals[cur] && animals[i])) continue; // 如果当前组合不可行跳过
        dp[cur][i] = true;
        dfs(i, dest, animals); // 尝试把当前位置的动物带过去，然后更新状态
    }
}

void solve() {
    vector<int> animals = {农民, 马, 羊, 牛};
    dp[农民][农民] = true;
    dfs(农民, 3, animals);
}

在这个例子中，`dfs` 函数代表深度优先搜索，它尝试将农夫、马、羊和牛分别放在`cur`位置到`dest`位置的所有可能组合上，检查每个组合是否合法并记录下来。最后调用`solve`函数初始化并开始求解。