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

以下是狼、羊、菜和农夫过河问题的C++代码实现，使用了BFS（广度优先搜索）算法：

#include <bits/stdc++.h>
using namespace std;

struct node {
    int wolf, sheep, vegetable, farmer, step; // 狼、羊、菜、农夫位置以及步数
};

bool vis[15][15][15][2]; // 记录状态是否出现过
bool is_valid(int wolf, int sheep, int vegetable) { // 判断当前状态是否合法
    if(wolf == sheep && wolf != vegetable) return false;
    if(sheep == vegetable && wolf != sheep) return false;
    return true;
}

int bfs(int wolf, int sheep, int vegetable) {
    queue<node> q;
    memset(vis, false, sizeof(vis));
    q.push({wolf, sheep, vegetable, 0, 0});
    vis[wolf][sheep][vegetable][0] = true;
    while(!q.empty()) {
        node cur = q.front();
        q.pop();
        if(cur.wolf == 1 && cur.sheep == 1 && cur.vegetable == 1) return cur.step;
        for(int i = 0; i < 2; i++) {
            int newfarmer = (cur.farmer + i) % 2;
            if(cur.wolf == cur.sheep && cur.wolf == newfarmer) continue;
            if(cur.vegetable == cur.sheep && cur.vegetable == newfarmer) continue;
            if(cur.vegetable == cur.wolf && cur.vegetable == newfarmer) continue;
            int newwolf = cur.wolf, newsheep = cur.sheep, newvegetable = cur.vegetable;
            if(newfarmer == 0) {
                newwolf = cur.wolf - i;
                newsheep = cur.sheep;
                newvegetable = cur.vegetable - i;
            } else {
                newwolf = cur.wolf + i;
                newsheep = cur.sheep + i;
                newvegetable = cur.vegetable;
            }
            if(newwolf < 0 || newwolf > 1 || newsheep < 0 || newsheep > 1 || newvegetable < 0 || newvegetable > 1) continue;
            if(!is_valid(newwolf, newsheep, newvegetable)) continue;
            if(vis[newwolf][newsheep][newvegetable][newfarmer]) continue;
            vis[newwolf][newsheep][newvegetable][newfarmer] = true;
            q.push({newwolf, newsheep, newvegetable, newfarmer, cur.step + 1});
        }
    }
    return -1;
}

int main() {
    int ans = bfs(1, 1, 1);
    printf("%d\n", ans);
    return 0;
}

其中，`vis`数组记录状态是否出现过，`is_valid`函数用于判断当前状态是否合法，`bfs`函数使用队列实现广度优先搜索，搜索过程中更新状态，并将新状态加入队列中，直到搜索到目标状态或者队列为空。最终输出最少需要多少步才能将狼、羊、菜和农夫运送到对岸。