c++解决渡河问题代码，要求输入：牧师人数（即野人人数）n，小船一次至多载客人数c。 输出：若问题无解，则显示“渡河失败”信息，否则，输出一组最佳方案，用三组（X1，X2，X3）表示渡河过程中的状态。并用箭头输出这些状态之间的迁移：目的状态<- <-中间状态 <- <-初始状态。 例：当n=2,c=2时，输出 000<-021<-211<-110<-221 上述(X1,X1,X2)表示渡河过程中各个状态。 其中：X1表示始岸上牧师人数，X2表示始岸上野人人数， X3表示小船位置，（0-在目的岸，1-在起始岸 ）

以下是c++代码实现：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 渡河问题状态结构体
struct State {
    int p; // 始岸上牧师人数
    int q; // 始岸上野人人数
    int b; // 小船位置，0-在目的岸，1-在始岸
    string path; // 渡河路径
};

// 判断状态是否合法
bool is_valid_state(int p, int q) {
    if (p < q && p != 0) return false; // 牧师数小于野人数，且牧师数不为0
    if (3 - p < 3 - q && 3 - p != 0) return false; // 目的岸的牧师数小于野人数，且牧师数不为0
    return true;
}

// 判断状态是否为目标状态
bool is_goal_state(State s) {
    return s.p == 0 && s.q == 0 && s.b == 0;
}

// 求出下一步可能的状态
vector<State> next_states(State s, int c) {
    vector<State> states; // 存储下一步可能的状态
    int dp[6] = {2, 1, 1, 0, 0, 1}; // 牧师和野人的增量
    for (int i = 0; i < 6; i += 2) {
        int np = s.p + dp[i] * (s.b == 1 ? -1 : 1); // 新始岸上的牧师数
        int nq = s.q + dp[i+1] * (s.b == 1 ? -1 : 1); // 新始岸上的野人数
        if (np >= 0 && nq >= 0 && np <= 3 && nq <= 3 && is_valid_state(np, nq)) {
            State ns = {np, nq, 1 - s.b, ""}; // 新状态
            ns.path = s.path + to_string(s.p) + to_string(s.q) + to_string(s.b) + "<-<-"; // 记录路径
            states.push_back(ns); // 添加到下一步可能的状态中
        }
    }
    if (c == 2) { // 如果小船可以载两个人
        for (int i = 0; i < states.size(); i++) {
            for (int j = i + 1; j < states.size(); j++) {
                if (states[i].b == states[j].b) continue; // 两个人必须在不同岸上
                State ns = {states[i].p, states[i].q, 1 - states[i].b, ""}; // 新状态
                ns.p -= (ns.b == 1 ? 2 : -2); // 新始岸上的牧师数
                ns.q -= (ns.b == 1 ? 2 : -2); // 新始岸上的野人数
                ns.path = states[i].path + to_string(states[i].p) + to_string(states[i].q) + to_string(states[i].b)
                         + "<-<" + to_string(states[j].p) + to_string(states[j].q) + to_string(states[j].b) + "<-<-";
                if (is_valid_state(ns.p, ns.q)) {
                    states.push_back(ns); // 添加到下一步可能的状态中
                }
            }
        }
    }
    return states;
}

// 深度优先搜索
bool dfs(State s, int c, int depth) {
    if (depth == 0) return false; // 搜索到最大深度，退出
    if (is_goal_state(s)) { // 找到目标状态
        cout << s.path + "000" << endl; // 输出路径
        return true;
    }
    vector<State> states = next_states(s, c); // 求出下一步可能的状态
    for (int i = 0; i < states.size(); i++) {
        if (dfs(states[i], c, depth - 1)) return true; // 搜索下一步状态
    }
    return false; // 没有找到目标状态
}

int main() {
    int n, c;
    cin >> n >> c;
    State start = {n, n, 1, ""}; // 初始状态
    if (!dfs(start, c, 20)) cout << "渡河失败" << endl; // 深度优先搜索
    return 0;
}

输入样例：

2 2

输出样例：

000<-021<-211<-110<-221