野人渡河问题c++

野人渡河问题，也称为“狼、羊、菜过河问题”，是一道经典的人工智能问题，常用于测试搜索算法。

问题描述：有一只船，可以坐两个人，船上有狼、羊、菜和一个人。当狼和羊在一起时，狼会吃掉羊；当羊和菜在一起时，羊会吃掉菜。现在需要将这四个物品都带到对岸，求最少需要几次才能完成。

以下是一个简单的 C++ 实现：

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

struct State {
    int boat; // 船在哪边，0表示左岸，1表示右岸
    int wolf; // 狼在哪边，0表示左岸，1表示右岸
    int goat; // 羊在哪边，0表示左岸，1表示右岸
    int cabbage; // 菜在哪边，0表示左岸，1表示右岸
    int step; // 走到当前状态需要的步数
    State(int b, int w, int g, int c, int s) : boat(b), wolf(w), goat(g), cabbage(c), step(s) {} // 构造函数
};

// 判断当前状态是否合法
bool isValid(const State& s) {
    if (s.wolf == s.goat && s.boat != s.wolf) return false; // 狼吃羊
    if (s.goat == s.cabbage && s.boat != s.goat) return false; // 羊吃菜
    return true;
}

// 判断两个状态是否相等
bool operator==(const State& s1, const State& s2) {
    return s1.boat == s2.boat && s1.wolf == s2.wolf && s1.goat == s2.goat && s1.cabbage == s2.cabbage;
}

// 哈希函数
struct Hash {
    size_t operator()(const State& s) const {
        return s.boat + s.wolf * 2 + s.goat * 4 + s.cabbage * 8;
    }
};

// BFS搜索
int bfs() {
    queue<State> q;
    set<State, Hash> visited;
    State start(0, 0, 0, 0, 0);
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        State cur = q.front();
        q.pop();

        if (cur.wolf && cur.goat && cur.cabbage && cur.boat) { // 找到了一个合法的状态，返回步数
            return cur.step;
        }

        vector<State> next(8, cur); // 枚举下一步可以到达的八个状态
        next[0].boat = !cur.boat; // 只有船过河
        next[0].step += 1;
        if (isValid(next[0]) && visited.find(next[0]) == visited.end()) {
            q.push(next[0]);
            visited.insert(next[0]);
        }

        next[1].boat = !cur.boat; // 船带狼过河
        next[1].wolf = !cur.wolf;
        next[1].step += 1;
        if (isValid(next[1]) && visited.find(next[1]) == visited.end()) {
            q.push(next[1]);
            visited.insert(next[1]);
        }

        next[2].boat = !cur.boat; // 船带羊过河
        next[2].goat = !cur.goat;
        next[2].step += 1;
        if (isValid(next[2]) && visited.find(next[2]) == visited.end()) {
            q.push(next[2]);
            visited.insert(next[2]);
        }

        next[3].boat = !cur.boat; // 船带菜过河
        next[3].cabbage = !cur.cabbage;
        next[3].step += 1;
        if (isValid(next[3]) && visited.find(next[3]) == visited.end()) {
            q.push(next[3]);
            visited.insert(next[3]);
        }

        next[4].boat = !cur.boat; // 船带狼和羊过河
        next[4].wolf = !cur.wolf;
        next[4].goat = !cur.goat;
        next[4].step += 1;
        if (isValid(next[4]) && visited.find(next[4]) == visited.end()) {
            q.push(next[4]);
            visited.insert(next[4]);
        }

        next[5].boat = !cur.boat; // 船带狼和菜过河
        next[5].wolf = !cur.wolf;
        next[5].cabbage = !cur.cabbage;
        next[5].step += 1;
        if (isValid(next[5]) && visited.find(next[5]) == visited.end()) {
            q.push(next[5]);
            visited.insert(next[5]);
        }

        next[6].boat = !cur.boat; // 船带羊和菜过河
        next[6].goat = !cur.goat;
        next[6].cabbage = !cur.cabbage;
        next[6].step += 1;
        if (isValid(next[6]) && visited.find(next[6]) == visited.end()) {
            q.push(next[6]);
            visited.insert(next[6]);
        }

        next[7].boat = !cur.boat; // 船带狼、羊和菜过河
        next[7].wolf = !cur.wolf;
        next[7].goat = !cur.goat;
        next[7].cabbage = !cur.cabbage;
        next[7].step += 1;
        if (isValid(next[7]) && visited.find(next[7]) == visited.end()) {
            q.push(next[7]);
            visited.insert(next[7]);
        }
    }

    return -1; // 无解
}

int main() {
    int step = bfs();
    if (step == -1) {
        cout << "无解" << endl;
    } else {
        cout << "最少需要 " << step << " 步" << endl;
    }
    return 0;
}

这个实现中使用了 BFS 算法进行搜索，不断地从队列中取出状态，判断是否为合法状态，如果是，就返回步数，否则，就枚举下一步可以到达的八个状态，判断是否为合法状态，如果是，就将其加入队列中。使用 set 来存储已经访问过的状态，避免重复搜索。