用c++代码处理传教士和野人过河问题

以下是用 C++ 语言实现传教士和野人过河问题的代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int M, C;
int ans[MAXN][MAXN];
bool vis[MAXN][MAXN];

void dfs(int ml, int cl, int mr, int cr, int step) {
    if (vis[ml][cl]) return;
    vis[ml][cl] = true;
    if (ml == 0 && cl == 0) {
        for (int i = 0; i <= step; i++) {
            cout << "Step " << i << ": ";
            for (int j = 1; j <= ans[i][0]; j++) {
                cout << "(" << ans[i][j] << "," << ans[i][j + 1] << ")";
                if (j != ans[i][0]) cout << " -> ";
            }
            cout << endl;
        }
        exit(0);
    }

    if (ml >= cl && ml < M && !vis[ml + 1][cl]) {
        ans[step][++ans[step][0]] = ml + 1;
        ans[step][++ans[step][0]] = cl;
        dfs(ml + 1, cl, mr - 1, cr, step + 1);
        ans[step][0] -= 2;
    }

    if (ml >= cl + 2 && !vis[ml][cl + 2]) {
        ans[step][++ans[step][0]] = ml;
        ans[step][++ans[step][0]] = cl + 2;
        dfs(ml, cl + 2, mr, cr - 2, step + 1);
        ans[step][0] -= 2;
    }

    if (cl >= ml + 2 && !vis[ml + 2][cl]) {
        ans[step][++ans[step][0]] = ml + 2;
        ans[step][++ans[step][0]] = cl;
        dfs(ml + 2, cl, mr - 2, cr, step + 1);
        ans[step][0] -= 2;
    }

    if (cl >= ml && cl < C && !vis[ml][cl + 1]) {
        ans[step][++ans[step][0]] = ml;
        ans[step][++ans[step][0]] = cl + 1;
        dfs(ml, cl + 1, mr, cr - 1, step + 1);
        ans[step][0] -= 2;
    }
}

int main() {
    cin >> M >> C;
    dfs(M, C, 0, 0, 1);
    return 0;
}

该代码中使用深度优先搜索（DFS）实现传教士和野人过河问题。vis[i][j] 表示在左岸有 i 个传教士和 j 个野人时是否已经访问过，ans[i][j] 则表示第 i 步的操作为将一个或两个人从左岸运到右岸，j 表示这一步操作的第 j 个元素。dfs 函数中的 if 语句分别对应着四种可能的情况：将一个传教士从左岸运到右岸、将两个野人从左岸运到右岸、将两个传教士从左岸运到右岸和将一个野人从左岸运到右岸。在每一次搜索中，如果当前状态已经访问过，则返回；如果已经到达目标状态（即左岸没有人了），则输出答案并结束程序；否则继续往下搜索。