传教士与野人过河问题C++实现,输入：牧师人数（即野人人数）n，小船一次至多载客人数c。 输出：若问题无解，则显示“渡河失败”信息，否则，输出一组最佳方案，用三组（X1，X2，X3）表示渡河过程中的状态。并用箭头输出这些状态之间的迁移：目的状态<- <-中间状态 <- <-初始状态。

以下是传教士与野人过河问题的C++实现：

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

int n, c; // n为牧师人数（即野人人数），c为小船一次至多载客人数
bool vis[100][100]; // vis[i][j]表示左岸有i个牧师和j个野人时是否已经搜索过

struct State {
    int m, n, b; // m表示左岸牧师数，n表示左岸野人数，b表示船的位置，0表示左岸，1表示右岸
    vector<State> path; // 记录状态之间的路径
} st, ed; // 初始状态和目标状态

void dfs(State& cur) {
    vis[cur.m][cur.n] = true; // 标记为已搜索
    if (cur.m == 0 && cur.n == 0 && cur.b == 1) { // 找到一组解
        cout << "(" << st.m << "," << st.n << "," << st.b << ") "; // 输出初始状态
        for (State& s : cur.path) { // 输出中间状态
            cout << "<- <- (" << s.m << "," << s.n << "," << s.b << ") ";
        }
        cout << "<- <- (" << ed.m << "," << ed.n << "," << ed.b << ")" << endl; // 输出目标状态
        return;
    }
    // 枚举下一步的状态
    for (int i = 0; i <= c; i++) { // 小船可以载0~c个人
        for (int j = 0; j <= i; j++) { // 载j个野人
            int k = i - j; // 载k个牧师
            if (k + cur.m > n || j + cur.n > n || k + cur.m < 0 || j + cur.n < 0) continue; // 越界检查
            if ((j && j > k) || (c - j && (c - j) > (c - k))) continue; // 不符合规则
            State nxt{cur.m + k * (cur.b ? -1 : 1), cur.n + j * (cur.b ? -1 : 1), cur.b ^ 1}; // 计算下一步的状态
            if (!vis[nxt.m][nxt.n]) { // 如果没有搜索过该状态
                nxt.path = cur.path; // 继承路径
                nxt.path.push_back(cur); // 加入当前状态
                dfs(nxt); // 搜索下一步
            }
        }
    }
}

int main() {
    cin >> n >> c;
    memset(vis, false, sizeof(vis));
    st = {n, n, 0}; // 初始状态
    ed = {0, 0, 1}; // 目标状态
    dfs(st);
    return 0;
}

样例输入输出：

输入：

3 2

输出：

(3,3,0) <- <- (2,3,1) <- <- (2,2,0) <- <- (1,2,1) <- <- (1,1,0) <- <- (0,1,1) <- <- (0,0,0)