c++写一段野人传教士过河问题的代码，要求只添加头文件#include <iostream>添加namespace std，使用cin和cout函数 定义结构体表示传教士、野人、各个状态 输入：牧师人数（即野人人数）n，小船一次至多载客人数c。 输出：若问题无解，则显示“渡河失败”信息，否则，输出一组最佳方案，用三组（X1，X2，X3）表示渡河过程中的状态。并用箭头输出这些状态之间的迁移：目的状态<- <-中间状态 <- <-初始状态。 例：当n=2,c=2时，输出 000<-021<-211<-110<-221 上述(X1,X1,X2)表示渡河过程中各个状态。 其中：X1表示始岸上牧师人数，X2表示始岸上野人人数， X3表示小船位置，（0-在目的岸，1-在起始岸 ）

以下是采用BFS算法实现的C++代码：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 105;
struct Node {
    int m, c, b, step; // m表示始岸上牧师人数，c表示始岸上野人人数，b表示小船位置，step表示当前步数
}start, target;

bool vis[MAXN][MAXN][2]; // vis数组用于标记每个状态是否已经遍历过
int n, c; // n表示牧师人数（即野人人数），c表示小船一次至多载客人数

void print_ans(Node &t, queue<Node> &q) {
    if (t.m == start.m && t.c == start.c && t.b == start.b) return; // 递归终止条件
    Node pre = q.front();
    q.pop();
    print_ans(pre, q);
    cout << pre.m << pre.c << pre.b << "<-<-";
}

bool check_valid(Node &u) { // 判断状态是否合法
    if (u.m < 0 || u.m > n || u.c < 0 || u.c > n) return false;
    if (u.m > 0 && u.m < u.c) return false;
    if (n - u.m > 0 && n - u.m < n - u.c) return false; // 剩余的牧师人数和野人人数同理
    return true;
}

void bfs() {
    queue<Node> q;
    memset(vis, false, sizeof(vis));
    start.step = 0;
    q.push(start);
    vis[start.m][start.c][start.b] = true;
    while (!q.empty()) {
        Node u = q.front();
        q.pop();
        if (u.m == target.m && u.c == target.c && u.b == target.b) { // 到达目标状态
            cout << start.m << start.c << start.b << "<-<-";
            print_ans(u, q);
            cout << u.m << u.c << u.b << endl;
            return;
        }
        Node v;
        v.b = u.b ^ 1; // 小船换岸
        v.step = u.step + 1;
        for (int i = 0; i <= c; i++) { // 枚举小船上的人数
            for (int j = 0; j <= c - i; j++) {
                int dm = v.b == 0 ? u.m - i : u.m + i; // 始岸或目的岸上的牧师人数
                int dc = v.b == 0 ? u.c - j : u.c + j; // 始岸或目的岸上的野人人数
                v.m = dm;
                v.c = dc;
                if (check_valid(v) && !vis[v.m][v.c][v.b]) {
                    vis[v.m][v.c][v.b] = true;
                    q.push(v);
                }
            }
        }
    }
    cout << "渡河失败" << endl;
}

int main() {
    cin >> n >> c;
    start.m = n;
    start.c = n;
    start.b = 1;
    target.m = target.c = 0;
    target.b = 0;
    bfs();
    return 0;
}

在运行程序时，输入牧师人数n和小船一次至多载客人数c，程序会输出一组最佳方案，用三组（X1，X2，X3）表示渡河过程中的状态，并用箭头输出这些状态之间的迁移。如果问题无解，则输出“渡河失败”信息。