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

好的，以下是用 C++ 实现的代码，同样采用深度优先搜索（DFS）算法： ```cpp #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 数组即可。