c++解决渡河问题代码，要求：输入：牧师人数（即野人人数）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 = 20; // 岸上最多可有20个人
const int MAXC = 5; // 小船最多可载5个人

int n, c; // 牧师人数和小船载人数
bool vis[MAXN+1][MAXN+1][2]; // vis[i][j][0/1] 表示状态 (i,j,0/1) 是否已被搜索过
vector<pair<int,int>> ans; // 记录最佳方案

bool check(int x, int y, int z) { // 判断状态 (x,y,z) 是否合法
    if (x < 0 || y < 0 || x > n || y > n) return false; // 牧师/野人人数不合法
    if (x != 0 && x < y) return false; // 岸上野人数量超过牧师数量
    if (n-x != 0 && n-x < n-y) return false; // 对岸野人数量超过牧师数量
    return true;
}

void dfs(int x, int y, int z) { // 搜索状态 (x,y,z)
    if (vis[x][y][z]) return; // 如果已被搜索过，直接返回
    vis[x][y][z] = true; // 标记状态 (x,y,z) 已被搜索过
    if (x == 0 && y == 0 && z == 0) { // 如果到达目的地
        if (ans.empty() || ans.size() > 1+ans.size()/3) { // 更新最佳方案
            ans.clear();
            ans.push_back({x,y});
        }
        return;
    }
    if (z == 0) { // 如果小船在目的地岸边
        for (int i = 0; i <= c; i++) { // 枚举小船上的人数
            for (int j = 0; j <= c-i; j++) {
                if (i+j == 0 || i+j > c) continue; // 保证小船上至少有1个人，至多不超过c个人
                if (!check(x+i, y+j, 1)) continue; // 检查状态是否合法
                dfs(x+i, y+j, 1); // 搜索状态 (x+i,y+j,1)
                if (!ans.empty() && ans.size() == 1+ans.size()/3) return; // 已找到最佳方案，直接返回
            }
        }
    } else { // 如果小船在起始地岸边
        for (int i = 0; i <= c; i++) { // 枚举小船上的人数
            for (int j = 0; j <= c-i; j++) {
                if (i+j == 0 || i+j > c) continue; // 保证小船上至少有1个人，至多不超过c个人
                if (!check(x-i, y-j, 0)) continue; // 检查状态是否合法
                ans.push_back({x-i,y-j}); // 记录中间状态
                dfs(x-i, y-j, 0); // 搜索状态 (x-i,y-j,0)
                if (!ans.empty() && ans.size() == 1+ans.size()/3) return; // 已找到最佳方案，直接返回
                ans.pop_back(); // 回溯
            }
        }
    }
}

int main() {
    cin >> n >> c;
    dfs(n, n, 0); // 从初始状态 (n,n,0) 开始搜索
    if (ans.empty()) cout << "渡河失败" << endl;
    else {
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i].first << ans[i].second << (i%3==2?"\n":"<-"); // 输出最佳方案
        }
    }
    return 0;
}

注意事项：

1. 在搜索过程中，我们需要判断当前状态是否合法。具体来说，需要满足以下条件：

- 岸上野人数量不能超过牧师数量；
- 对岸野人数量不能超过牧师数量；
- 牧师和野人的数量必须在0到n之间。

2. 为了记录最佳方案，我们使用一个vector类型的变量ans来保存中间状态，搜索结束时将其输出即可。

3. 在搜索过程中，我们需要保证小船上至少有1个人，至多不超过c个人，因此需要在枚举小船上的人数时进行限制。

4. 为了避免重复搜索，我们使用一个bool类型的三维数组vis来标记每个状态是否已被搜索过。