用c++实现 假如有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数（除非牧师人数为0），且假定两种人都会划船，试设计一个算法，确定它们能否渡过河去，若能，则给出一只小船来回次数最少的最佳方案。 ◎基本要求 输入：牧师人数（即野人人数）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>
using namespace std;

const int MAXN = 10;

int n, c; // 牧师人数和小船载客人数
int boat_pos; // 小船位置，1表示在起始岸，0表示在目的岸
int priests[MAXN], devils[MAXN]; // 牧师和野人的状态
int priests_on_boat, devils_on_boat; // 小船上的牧师和野人数量

vector<pair<int, int>> path; // 记录路径

bool is_valid() { // 判断当前状态是否合法
    if (priests[0] < devils[0] || priests[1] < devils[1]) return false;
    if (priests_on_boat < devils_on_boat && priests_on_boat > 0) return false;
    if (priests_on_boat + devils_on_boat > c) return false;
    return true;
}

bool dfs() {
    if (priests[0] == 0 && devils[0] == 0) return true; // 所有人都已到达目的岸
    if (!is_valid()) return false; // 当前状态不合法

    // 尝试从当前状态转移到下一个状态
    for (int i = 0; i <= priests_on_boat; i++) { // 枚举小船上的牧师数量
        for (int j = 0; j <= devils_on_boat; j++) { // 枚举小船上的野人数量
            if (i + j == 0) continue; // 小船上至少有一个人
            if (i + j > c) continue; // 小船上最多只能有c个人
            if (i > 0 && i < j) continue; // 牧师人数不能少于野人人数

            // 尝试把i个牧师和j个野人从当前岸移动到另一个岸
            priests[boat_pos] -= i;
            devils[boat_pos] -= j;
            priests[1 - boat_pos] += i;
            devils[1 - boat_pos] += j;
            boat_pos = 1 - boat_pos;
            priests_on_boat = i;
            devils_on_boat = j;
            path.push_back({priests[0] * 100 + devils[0], boat_pos}); // 记录路径

            if (dfs()) return true; // 搜索下一个状态
            else { // 回溯
                boat_pos = 1 - boat_pos;
                priests[1 - boat_pos] -= i;
                devils[1 - boat_pos] -= j;
                priests[boat_pos] += i;
                devils[boat_pos] += j;
                priests_on_boat = 0;
                devils_on_boat = 0;
                path.pop_back();
            }
        }
    }

    return false; // 没有找到下一个合法状态
}

int main() {
    cin >> n >> c;

    priests[0] = priests[1] = n;
    devils[0] = devils[1] = n;
    boat_pos = 1; // 小船初始位置为起始岸
    priests_on_boat = 0;
    devils_on_boat = 0;

    if (dfs()) { // 搜索成功
        for (int i = 0; i < path.size(); i++) {
            int p = path[i].first / 100, d = path[i].first % 100;
            cout << p << d << path[i].second;
            if (i < path.size() - 1) cout << "<-<-";
        }
    } else { // 搜索失败
        cout << "渡河失败";
    }

    return 0;
}

输入格式如下：

2 2

输出结果如下：

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