用c++实现假如有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数（除非牧师人数为0），且假定两种人都会划船，试设计一个算法，确定它们能否渡过河去，若能，则给出一只小船来回次数最少的最佳方案。输入：牧师人数（即野人人数）n，小船一次至多载客人数c。 输出：若问题无解，则显示“渡河失败”信息，否则，输出一组最佳方案，用三组（X1，X2，X3）表示渡河过程中的状态。并用箭头输出这些状态之间的迁移：目的状态<- <-中间状态 <- <-初始状态。

好的，以下是用 C++ 实现的代码，同样采用深度优先搜索（DFS）算法：

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

const int MAXN = 105;
int n, c, count = MAXN; // count 记录船来回的次数
bool vis[MAXN][MAXN]; // vis[i][j] 表示状态 (i, j, 0/1) 是否已经访问过
vector<pair<int, int>> ans; // 存储最佳方案

void dfs(int m, int cn, int b, int step) {
    if (step >= count) return; // 船来回次数已经大于等于最佳方案，直接返回
    if (m < 0 || m > n || cn < 0 || cn > n) return; // 牧师或野人数量不合法，返回
    if (m > 0 && m < cn) return; // 牧师数量小于野人数量，返回
    if (vis[m][cn]) return; // 状态已经访问过，返回
    vis[m][cn] = true; // 标记状态已经访问过
    if (m == 0 && cn == 0 && b == 1) { // 找到一组最佳方案
        count = step; // 更新船来回次数
        ans.clear(); // 清空最佳方案
        return;
    }
    if (b == 0) { // 船在左岸
        dfs(m, cn - 1, 1, step + 1); // 带一个野人过河
        dfs(m - 1, cn, 1, step + 1); // 带一个牧师过河
        dfs(m - 2, cn, 1, step + 1); // 带两个牧师过河
        dfs(m, cn - 2, 1, step + 1); // 带两个野人过河
        dfs(m - 1, cn - 1, 1, step + 1); // 带一个牧师和一个野人过河
    } else { // 船在右岸
        dfs(m, cn + 1, 0, step + 1); // 带一个野人过河
        dfs(m + 1, cn, 0, step + 1); // 带一个牧师过河
        dfs(m + 2, cn, 0, step + 1); // 带两个牧师过河
        dfs(m, cn + 2, 0, step + 1); // 带两个野人过河
        dfs(m + 1, cn + 1, 0, step + 1); // 带一个牧师和一个野人过河
    }
    vis[m][cn] = false; // 回溯
    ans.push_back({m, cn}); // 记录状态
}

int main() {
    cin >> n >> c;
    dfs(n, n, 0, 0); // 从初始状态开始搜索
    if (count == MAXN) cout << "渡河失败" << endl;
    else {
        cout << "(0, 0, 1) <- <- ";
        for (auto p: ans) {
            cout << "(" << p.first << ", " << p.second << ", ";
            if (p.first > p.second) cout << "1)";
            else cout << "0)";
            cout << " <- <- ";
        }
        cout << "(n, n, 0)" << endl;
    }
    return 0;
}

注意，这里的 vis 数组需要初始化为 false，否则会出错。另外，题目要求输出状态之间的转移，我们可以将每个状态（除了初始状态和最终状态）存储到 ans 数组中，最后输出时遍历 ans 数组即可。