传教士与野人过河问题c++实现

传教士与野人过河问题是一个经典的逻辑问题，可以利用深度优先搜索或广度优先搜索等算法来解决。下面是一份使用深度优先搜索解决传教士与野人过河问题的C++代码示例：

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

const int MAXN = 1e4 + 5;
const int dx[] = { 0, 0, -1, 1 };
const int dy[] = { -1, 1, 0, 0 };

int M, C; // 初始左岸传教士和野人数量
bool vis[MAXN][MAXN]; // vis[i][j]表示i个传教士、j个野人是否搜索过

bool check(int m, int c) { // 判断状态是否合法
    return m >= 0 && c >= 0 && M - m >= C - c && M - m >= 0 && C - c >= 0;
}

void dfs(int m, int c) {
    if (m == M && c == C) { // 到达目标状态
        cout << "Success!" << endl;
        return;
    }
    vis[m][c] = true;
    for (int i = 0; i < 4; i++) { // 枚举下一步的状态
        int nm = m - dx[i], nc = c - dy[i];
        if (!vis[nm][nc] && check(nm, nc)) {
            dfs(nm, nc);
        }
    }
}

int main() {
    memset(vis, false, sizeof(vis));
    cin >> M >> C;
    dfs(M, C);
    return 0;
}

在上述代码中，我们使用一个布尔型二维数组`vis`来记录每个状态是否已经被搜索过，以避免重复搜索。函数`check`用于判断当前状态是否合法，即当前左岸传教士和野人数量是否满足要求。在函数`dfs`中，我们首先标记当前状态已经被搜索过，然后枚举下一步可能的状态，并逐一进行递归搜索。如果到达目标状态，则输出“Success!”；否则程序将继续搜索。