[C言語] 宣教師と人食い人問題を解くアルゴリズムの実装

#include <stdio.h>
// 状態を表現する構造体
typedef struct {
    int missionaries; // 宣教師の数
    int cannibals;    // 人食い人の数
    int boat;         // ボートの位置 (0: 現在の岸, 1: 向こう岸)
} State;

// 状態が有効かどうかをチェックする関数
int isValidState(State state) {
    // 宣教師と人食い人の数が負でないかチェック
    if (state.missionaries < 0 || state.cannibals < 0) return 0;
    // 宣教師と人食い人の数が3を超えないかチェック
    if (state.missionaries > 3 || state.cannibals > 3) return 0;
    // 宣教師が人食い人より少ない場合は無効
    if (state.missionaries < state.cannibals && state.missionaries > 0) return 0;
    // 向こう岸でも同様のチェック
    if ((3 - state.missionaries) < (3 - state.cannibals) && (3 - state.missionaries) > 0) return 0;
    return 1;
}

// 状態遷移を行う関数
State move(State current, int missionaries, int cannibals) {
    State newState = current;
    // ボートの位置に応じて宣教師と人食い人を移動
    if (current.boat == 0) {
        newState.missionaries -= missionaries;
        newState.cannibals -= cannibals;
        newState.boat = 1;
    } else {
        newState.missionaries += missionaries;
        newState.cannibals += cannibals;
        newState.boat = 0;
    }
    return newState;
}

#include <stdbool.h>
// 状態を記録するための配列
bool visited[4][4][2];
// 状態が訪問済みかどうかをチェックする関数
bool isVisited(State state) {
    return visited[state.missionaries][state.cannibals][state.boat];
}
// 状態を訪問済みにする関数
void markVisited(State state) {
    visited[state.missionaries][state.cannibals][state.boat] = true;
}

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct {
    int missionaries;
    int cannibals;
    int boat;
} State;
typedef struct Node {
    State state;
    struct Node* parent;
} Node;
typedef struct {
    Node* nodes[100];
    int front;
    int rear;
} Queue;
void enqueue(Queue* q, Node* node) {
    q->nodes[q->rear++] = node;
}
Node* dequeue(Queue* q) {
    return q->nodes[q->front++];
}
bool isQueueEmpty(Queue* q) {
    return q->front == q->rear;
}
bool visited[4][4][2];
bool isValidState(State state) {
    if (state.missionaries < 0 || state.cannibals < 0) return false;
    if (state.missionaries > 3 || state.cannibals > 3) return false;
    if (state.missionaries < state.cannibals && state.missionaries > 0) return false;
    if ((3 - state.missionaries) < (3 - state.cannibals) && (3 - state.missionaries) > 0) return false;
    return true;
}
bool isVisited(State state) {
    return visited[state.missionaries][state.cannibals][state.boat];
}
void markVisited(State state) {
    visited[state.missionaries][state.cannibals][state.boat] = true;
}
State move(State current, int missionaries, int cannibals) {
    State newState = current;
    if (current.boat == 0) {
        newState.missionaries -= missionaries;
        newState.cannibals -= cannibals;
        newState.boat = 1;
    } else {
        newState.missionaries += missionaries;
        newState.cannibals += cannibals;
        newState.boat = 0;
    }
    return newState;
}
void printSolution(Node* node) {
    if (node == NULL) return;
    printSolution(node->parent);
    printf("M: %d, C: %d, B: %d\n", node->state.missionaries, node->state.cannibals, node->state.boat);
}
void solve() {
    Queue q = { .front = 0, .rear = 0 };
    State initialState = {3, 3, 0};
    Node* initialNode = (Node*)malloc(sizeof(Node));
    initialNode->state = initialState;
    initialNode->parent = NULL;
    enqueue(&q, initialNode);
    markVisited(initialState);
    while (!isQueueEmpty(&q)) {
        Node* currentNode = dequeue(&q);
        State currentState = currentNode->state;
        if (currentState.missionaries == 0 && currentState.cannibals == 0 && currentState.boat == 1) {
            printSolution(currentNode);
            return;
        }
        int moves[5][2] = {{1, 0}, {2, 0}, {0, 1}, {0, 2}, {1, 1}};
        for (int i = 0; i < 5; i++) {
            State newState = move(currentState, moves[i][0], moves[i][1]);
            if (isValidState(newState) && !isVisited(newState)) {
                Node* newNode = (Node*)malloc(sizeof(Node));
                newNode->state = newState;
                newNode->parent = currentNode;
                enqueue(&q, newNode);
                markVisited(newState);
            }
        }
    }
    printf("解が見つかりませんでした。\n");
}
int main() {
    solve();
    return 0;
}