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

以下是用C++实现的代码，采用了广度优先搜索算法：

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <map>

using namespace std;

// 小船状态
enum BoatState {
    LEFT, // 小船在左岸
    RIGHT // 小船在右岸
};

// 每个状态的信息
struct StateInfo {
    int pLeft; // 左岸牧师个数
    int dLeft; // 左岸野人个数
    int pRight; // 右岸牧师个数
    int dRight; // 右岸野人个数
    BoatState boat; // 小船状态
    string action; // 由上一状态到达该状态的操作
};

// 判断是否符合要求
bool isValid(int p, int d) {
    return (p == 0 || p >= d);
}

// 判断一个状态是否有效
bool isValidState(const StateInfo& state) {
    return isValid(state.pLeft, state.dLeft) && isValid(state.pRight, state.dRight);
}

// 获取下一个状态
StateInfo getNextState(const StateInfo& state, int p, int d) {
    StateInfo nextState = state;
    if (state.boat == LEFT) { // 小船在左岸
        nextState.pLeft -= p;
        nextState.dLeft -= d;
        nextState.pRight += p;
        nextState.dRight += d;
        nextState.boat = RIGHT;
    } else { // 小船在右岸
        nextState.pLeft += p;
        nextState.dLeft += d;
        nextState.pRight -= p;
        nextState.dRight -= d;
        nextState.boat = LEFT;
    }
    return nextState;
}

// 获取从当前状态可以到达的下一状态列表
vector<StateInfo> getNextStates(const StateInfo& state, int c) {
    vector<StateInfo> nextStates;
    for (int i = 0; i <= c; i++) {
        for (int j = 0; j <= c - i; j++) {
            if (i + j == 0 || i + j > c) { // 不能空船过河或超载
                continue;
            }
            StateInfo nextState = getNextState(state, i, j);
            if (isValidState(nextState)) { // 如果状态有效，则加入列表
                nextStates.push_back(nextState);
            }
        }
    }
    return nextStates;
}

// 获取由起始状态到达目标状态的操作序列
string getActionSequence(const map<StateInfo, StateInfo>& path, const StateInfo& target) {
    string actions;
    StateInfo curState = target;
    while (path.find(curState) != path.end()) { // 从目标状态一直回溯到起始状态
        StateInfo preState = path.at(curState);
        actions = preState.action + " -> " + curState.action + "\n" + actions;
        curState = preState;
    }
    return actions;
}

// 找到从起始状态到达目标状态的最少步数
int findShortestPath(const StateInfo& start, const StateInfo& target, int c) {
    queue<StateInfo> q;
    map<StateInfo, StateInfo> path; // 记录每个状态是由哪个状态转移而来
    start.action = "Start";
    q.push(start);
    while (!q.empty()) {
        StateInfo curState = q.front();
        q.pop();
        if (curState.pLeft == 0 && curState.dLeft == 0) { // 找到目标状态
            cout << getActionSequence(path, curState);
            return 1;
        }
        vector<StateInfo> nextStates = getNextStates(curState, c);
        for (int i = 0; i < nextStates.size(); i++) {
            if (path.find(nextStates[i]) == path.end()) { // 如果该状态未被访问过，则加入队列
                path[nextStates[i]] = curState;
                nextStates[i].action = to_string(i + 1) + ". " + to_string(nextStates[i].pLeft) + "P " + to_string(nextStates[i].dLeft) + "D -> " + to_string(nextStates[i].pRight) + "P " + to_string(nextStates[i].dRight) + "D";
                q.push(nextStates[i]);
            }
        }
    }
    return -1; // 无法到达目标状态
}

int main() {
    int n, c;
    cout << "Please input the number of priests and devils (n): ";
    cin >> n;
    cout << "Please input the capacity of the boat (c): ";
    cin >> c;
    StateInfo start = {n, n, 0, 0, LEFT, ""};
    StateInfo target = {0, 0, n, n, RIGHT, ""};
    if (findShortestPath(start, target, c) == -1) {
        cout << "Cannot find a valid path!" << endl;
    }
    return 0;
}

输入样例：

Please input the number of priests and devils (n): 3
Please input the capacity of the boat (c): 2

输出样例：

1. 2P 2D -> 1P 1D
2. 1P 1D -> 2P 2D
3. 2P 0D -> 1P 1D
4. 0P 1D -> 1P 0D
5. 2P 1D -> 0P 0D