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

传教士与野人过河问题是一个经典的智力游戏。在这个问题中，有三个传教士和三个野人要过一条河流，但是船只只能容纳两个人，且必须有至少一个人在船上才能移动。另外，如果传教士的人数少于野人的人数，那么传教士就会被野人吃掉。问如何安排才能让所有人都过河，而且不出现传教士被野人吃掉的情况。

以下是一个基于深度优先搜索的 C++ 解法：

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

const int MAXN = 10;  // 最多6个人，加上船，最多有7个物品
int f[MAXN][MAXN][MAXN];  // f数组用于标记某种状态是否已经搜索过
int pre[MAXN][MAXN][MAXN][3];  // pre数组用于记录某种状态的前驱状态

void dfs(int m1, int c1, int b, int m2, int c2) {  // 从(m1, c1, b, m2, c2)出发
    if (f[m1][c1][b]) return;  // 如果已经搜索过了，就返回
    f[m1][c1][b] = 1;  // 标记搜索过了

    if (m1 == 0 && c1 == 0) {  // 如果传教士和野人都到达了对岸，输出方案并结束
        cout << "Solution: " << endl;
        cout << "ML CL BOAT MR CR" << endl;
        for (int i = 0; i < 6; i++) {
            cout << pre[m1][c1][b][0] << "  " << pre[m1][c1][b][1] << "  " << pre[m1][c1][b][2] << "   " << pre[m2][c2][!b][0] << "  " << pre[m2][c2][!b][1] << endl;
            int t1 = m1 - pre[m1][c1][b][0], t2 = c1 - pre[m1][c1][b][1], t3 = b - pre[m1][c1][b][2];
            int t4 = m2 - pre[m2][c2][!b][0], t5 = c2 - pre[m2][c2][!b][1], t6 = !b - pre[m2][c2][!b][2];
            m1 = t1, c1 = t2, b = t3, m2 = t4, c2 = t5, b = t6;
        }
        cout << endl;
        return;
    }

    if (m1 > 0) {  // 尝试带一个传教士过河
        int nm1 = m1 - 1, nc1 = c1, nb = !b, nm2 = m2 + 1, nc2 = c2;
        if (nm1 >= nc1 && (nm2 >= nc2 || nm2 == 0)) {  // 判断状态是否合法
            pre[nm1][nc1][nb][0] = m1, pre[nm1][nc1][nb][1] = c1, pre[nm1][nc1][nb][2] = b;
            dfs(nm1, nc1, nb, nm2, nc2);
        }
    }
    if (c1 > 0) {  // 尝试带一个野人过河
        int nm1 = m1, nc1 = c1 - 1, nb = !b, nm2 = m2, nc2 = c2 + 1;
        if (nm1 >= nc1 && (nm2 >= nc2 || nm2 == 0)) {  // 判断状态是否合法
            pre[nm1][nc1][nb][0] = m1, pre[nm1][nc1][nb][1] = c1, pre[nm1][nc1][nb][2] = b;
            dfs(nm1, nc1, nb, nm2, nc2);
        }
    }
    if (m1 > 1) {  // 尝试带两个传教士过河
        int nm1 = m1 - 2, nc1 = c1, nb = !b, nm2 = m2 + 2, nc2 = c2;
        if (nm1 >= nc1 && (nm2 >= nc2 || nm2 == 0)) {  // 判断状态是否合法
            pre[nm1][nc1][nb][0] = m1, pre[nm1][nc1][nb][1] = c1, pre[nm1][nc1][nb][2] = b;
            dfs(nm1, nc1, nb, nm2, nc2);
        }
    }
    if (c1 > 1) {  // 尝试带两个野人过河
        int nm1 = m1, nc1 = c1 - 2, nb = !b, nm2 = m2, nc2 = c2 + 2;
        if (nm1 >= nc1 && (nm2 >= nc2 || nm2 == 0)) {  // 判断状态是否合法
            pre[nm1][nc1][nb][0] = m1, pre[nm1][nc1][nb][1] = c1, pre[nm1][nc1][nb][2] = b;
            dfs(nm1, nc1, nb, nm2, nc2);
        }
    }
    if (m1 > 0 && c1 > 0) {  // 尝试带一个传教士和一个野人过河
        int nm1 = m1 - 1, nc1 = c1 - 1, nb = !b, nm2 = m2 + 1, nc2 = c2 + 1;
        if (nm1 >= nc1 && (nm2 >= nc2 || nm2 == 0)) {  // 判断状态是否合法
            pre[nm1][nc1][nb][0] = m1, pre[nm1][nc1][nb][1] = c1, pre[nm1][nc1][nb][2] = b;
            dfs(nm1, nc1, nb, nm2, nc2);
        }
    }
}

int main() {
    memset(f, 0, sizeof(f));  // 初始化f数组为0
    dfs(3, 3, 0, 0, 0);  // 从(3, 3, 0, 0, 0)出发
    return 0;
}

该程序会输出所有能够到达对岸的方案。其中，“ML”表示左岸的传教士数量，“CL”表示左岸的野人数量，“BOAT”表示船的位置，0表示左岸，1表示右岸，“MR”表示右岸的传教士数量，“CR”表示右岸的野人数量。