传教士与野人过河问题c语言

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

#include <stdio.h>
#include <stdlib.h>

#define N 3 //传教士和野人的数量
#define BOAT_SIZE 2 //船的容量

int boat[BOAT_SIZE]; //船上的人数
int left[N] = { N, N, 1 }; //左岸的人数
int right[N] = { 0, 0, 0 }; //右岸的人数

void print() //输出当前状态
{
    printf("Left: ");
    for (int i = 0; i < N; i++) {
        if (left[i]) {
            printf("%d ", i + 1);
        }
    }
    printf("\n");
    printf("Right: ");
    for (int i = 0; i < N; i++) {
        if (right[i]) {
            printf("%d ", i + 1);
        }
    }
    printf("\n");
    printf("Boat: ");
    for (int i = 0; i < BOAT_SIZE; i++) {
        if (boat[i]) {
            printf("%d ", boat[i]);
        }
    }
    printf("\n\n");
}

int check(int l[N], int r[N]) //检查当前状态是否合法
{
    if ((l[0] && l[1] && l[0] < l[1]) || (r[0] && r[1] && r[0] < r[1])) {
        return 0; //传教士被野人吃掉了
    }
    if ((l[1] && l[2] && l[1] < l[2]) || (r[1] && r[2] && r[1] < r[2])) {
        return 0; //野人太多了
    }
    return 1; //状态合法
}

void dfs(int d, int s) //深度优先搜索
{
    if (d <= 0) { //搜索完毕
        print(); //输出最终状态
        return;
    }
    for (int i = 0; i < N; i++) { //枚举传教士
        if (left[i]) { //当前岸上有传教士
            left[i]--; //将传教士带到船上
            boat[s++] = i + 1;
            for (int j = 0; j < N; j++) { //枚举野人
                if (left[j]) { //当前岸上有野人
                    left[j]--; //将野人带到船上
                    boat[s++] = -j - 1;
                    if (check(left, right)) { //状态合法
                        dfs(d - 1, s); //继续搜索
                    }
                    boat[--s] = 0; //回溯
                    left[j]++; //回溯
                }
            }
            boat[--s] = 0; //回溯
            left[i]++; //回溯
        }
    }
}

int main()
{
    printf("Missionaries and Cannibals Problem\n\n");
    printf("Legend:\n");
    printf("  M - Missionaries\n");
    printf("  C - Cannibals\n");
    printf("  B - Boat\n\n");
    dfs(BOAT_SIZE, 0); //从左岸开始搜索
    return 0;
}

代码中使用了深度优先搜索来枚举所有可能的状态，然后对每个状态进行检查，判断是否合法。如果状态合法，则继续搜索下一层。最终输出所有可行的状态。