传教士和野人过河问题用c语言写份代码

"传教士和野人过河"是一个经典的算法设计题目，它涉及到了回溯法和状态转移的思想。这个问题描述的是有三个人（传教士、野人和另一个传教士），其中两个人不会游泳，需要一艘船才能过河。但是每次只能带一个人过河，而且船没有人划的时候，必须有人留在对岸照看。

下面是一个简单的 C 语言版本的解决方案：

#include <stdio.h>

#define MAX 4 // 情况总数
int dp[MAX][MAX]; // 动态规划数组

// 定义情况：0 - 无人过河，1 - 传教士1，2 - 野人，3 - 传教士2
void move(int a, int b) {
    printf("Move %d to the other side with %d\n", a + 1, b + 1);
}

int canCross(int state) {
    if (dp[state][state] != -1) return dp[state][state];
    if (state == 3) { // 如果只剩传教士2，就直接过去
        dp[state][state] = 1;
        return 1;
    }
    for (int i = 0; i <= state; i++) { // 遍历所有可能性
        if (i == 1 || i == 2 || (state - i) == 1 || (state - i) == 2) { // 只考虑非冲突组合
            if (canCross(i) && canCross(state - i)) { // 如果两边的人都能过河
                dp[state][state] = 1; // 成功过河
                move(state, i); // 记录行动
                break;
            }
        }
    }
    return dp[state][state];
}

int main() {
    memset(dp, -1, sizeof(dp)); // 初始化动态规划表
    if (canCross(0)) {
        printf("Solution exists!\n");
    } else {
        printf("No solution exists.\n");
    }
    return 0;
}

这个代码首先初始化了一个动态规划表格 `dp` 来存储从初始状态到结束状态是否可行。函数 `move()` 描述了当前操作，`canCross()` 则通过递归尝试各种组合来判断是否能找到解决方案。