用c++代码实现假如有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数（除非牧师人数为0），且假定两种人都会划船，试设计一个算法，确定它们能否渡过河去，若能，则给出一只小船来回次数最少的最佳方案。

以下是一个基于DFS的解法，代码中使用了vector来存储船上的人员，方便操作和输出。

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 10;

int n, c; // n个牧师和n个野人，小船容纳c个人
bool visited[MAXN + 1][MAXN + 1];
vector<int> left_bank; // 左岸人员
vector<int> right_bank; // 右岸人员

bool check(vector<int>& bank) { // 检查当前状态是否合法
    int p = 0, m = 0;
    for (int i = 0; i < bank.size(); i++) {
        if (bank[i] == 1) p++;
        else m++;
    }
    if (p < m) return false;
    if (n - p < n - m) return false;
    return true;
}

void dfs(int step) {
    if (right_bank.size() == n) { // 右岸已经全部通过
        cout << "Solution:\n";
        for (int i = 0; i < right_bank.size(); i++) {
            cout << right_bank[i];
        }
        cout << endl;
        return;
    }
    if (step % 2 == 0) { // 船在左岸
        for (int i = 0; i < left_bank.size(); i++) {
            for (int j = 0; j < left_bank.size(); j++) {
                if (i == j) continue; // 不能选择同一个人
                vector<int> temp = left_bank;
                vector<int> boat;
                boat.push_back(temp[i]);
                boat.push_back(temp[j]);
                for (int k = 0; k < boat.size(); k++) {
                    temp.erase(find(temp.begin(), temp.end(), boat[k]));
                }
                if (check(temp) && !visited[temp.size()][boat.size()]) { // 检查合法性
                    visited[temp.size()][boat.size()] = true;
                    right_bank.insert(right_bank.end(), boat.begin(), boat.end());
                    dfs(step + 1);
                    visited[temp.size()][boat.size()] = false;
                    for (int k = 0; k < boat.size(); k++) {
                        right_bank.pop_back();
                    }
                }
            }
        }
    } else { // 船在右岸
        for (int i = 0; i < right_bank.size(); i++) {
            for (int j = 0; j < right_bank.size(); j++) {
                if (i == j) continue;
                vector<int> temp = right_bank;
                vector<int> boat;
                boat.push_back(temp[i]);
                boat.push_back(temp[j]);
                for (int k = 0; k < boat.size(); k++) {
                    temp.erase(find(temp.begin(), temp.end(), boat[k]));
                }
                if (check(temp) && !visited[temp.size()][c - boat.size()]) {
                    visited[temp.size()][c - boat.size()] = true;
                    left_bank.insert(left_bank.end(), boat.begin(), boat.end());
                    dfs(step + 1);
                    visited[temp.size()][c - boat.size()] = false;
                    for (int k = 0; k < boat.size(); k++) {
                        left_bank.pop_back();
                    }
                }
            }
        }
    }
}

int main() {
    cout << "Please input the number of people and the capacity of the boat:" << endl;
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        left_bank.push_back(1);
        left_bank.push_back(0);
    }
    dfs(0);
    return 0;
}

代码中使用的visited数组用来记录当前状态是否已经被访问过，避免重复搜索，同时也可以剪枝。