請用JAVA編寫牧師野人過河問題的完整程序

以下是牧师野人过河问题的Java程序：

import java.util.*;

public class MissionaryCannibal {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入牧师数量：");
        int missionaryNum = scanner.nextInt();
        System.out.print("请输入野人数量：");
        int cannibalNum = scanner.nextInt();

        State initialState = new State(missionaryNum, cannibalNum, true, 0, 0);
        State finalState = breadthFirstSearch(initialState);

        if (finalState != null) {
            List<State> path = new ArrayList<>();
            State state = finalState;
            while (state != null) {
                path.add(state);
                state = state.getParent();
            }
            Collections.reverse(path);
            for (State s : path) {
                System.out.println(s);
            }
        } else {
            System.out.println("无解");
        }
    }

    private static State breadthFirstSearch(State initialState) {
        Queue<State> queue = new LinkedList<>();
        Set<State> visited = new HashSet<>();
        queue.offer(initialState);
        visited.add(initialState);

        while (!queue.isEmpty()) {
            State state = queue.poll();
            if (state.isFinalState()) {
                return state;
            }
            List<State> nextStates = getNextStates(state);
            for (State nextState : nextStates) {
                if (!visited.contains(nextState)) {
                    queue.offer(nextState);
                    visited.add(nextState);
                }
            }
        }

        return null;
    }

    private static List<State> getNextStates(State state) {
        List<State> nextStates = new ArrayList<>();
        int m = state.getM();
        int c = state.getC();
        boolean b = state.isBoatOnTheLeftBank();
        int ml = b ? m - 1 : m + 1;
        int cl = b ? c - 1 : c + 1;

        // 一个牧师过河
        if (ml >= 0 && ml <= 3 && cl >= 0 && cl <= 3 && ml >= cl) {
            State nextState = new State(ml, cl, !b, state.getMisOnTheLeftBank() - (b ? 1 : 0), state.getCannOnTheLeftBank() - (b ? 1 : 0));
            nextState.setParent(state);
            nextStates.add(nextState);
        }

        // 两个牧师过河
        ml = b ? m - 2 : m + 2;
        cl = c;
        if (ml >= 0 && ml <= 3 && cl >= 0 && cl <= 3 && ml >= cl) {
            State nextState = new State(ml, cl, !b, state.getMisOnTheLeftBank() - (b ? 2 : 0), state.getCannOnTheLeftBank() - (b ? 2 : 0));
            nextState.setParent(state);
            nextStates.add(nextState);
        }

        // 一个野人过河
        ml = m;
        cl = b ? c - 1 : c + 1;
        if (ml >= 0 && ml <= 3 && cl >= 0 && cl <= 3 && ml >= cl) {
            State nextState = new State(ml, cl, !b, state.getMisOnTheLeftBank(), state.getCannOnTheLeftBank() - (b ? 1 : 0));
            nextState.setParent(state);
            nextStates.add(nextState);
        }

        // 一位野人和一位牧师过河
        ml = b ? m - 1 : m + 1;
        cl = b ? c - 1 : c + 1;
        if (ml >= 0 && ml <= 3 && cl >= 0 && cl <= 3 && ml >= cl) {
            State nextState = new State(ml, cl, !b, state.getMisOnTheLeftBank() - (b ? 1 : 0), state.getCannOnTheLeftBank() - (b ? 1 : 0));
            nextState.setParent(state);
            nextStates.add(nextState);
        }

        // 两位野人过河
        ml = m;
        cl = b ? c - 2 : c + 2;
        if (ml >= 0 && ml <= 3 && cl >= 0 && cl <= 3 && ml >= cl) {
            State nextState = new State(ml, cl, !b, state.getMisOnTheLeftBank(), state.getCannOnTheLeftBank() - (b ? 2 : 0));
            nextState.setParent(state);
            nextStates.add(nextState);
        }

        return nextStates;
    }

    private static class State {
        private final int m;
        private final int c;
        private final boolean boatOnTheLeftBank;
        private final int misOnTheLeftBank;
        private final int cannOnTheLeftBank;
        private State parent;

        public State(int m, int c, boolean boatOnTheLeftBank, int misOnTheLeftBank, int cannOnTheLeftBank) {
            this.m = m;
            this.c = c;
            this.boatOnTheLeftBank = boatOnTheLeftBank;
            this.misOnTheLeftBank = misOnTheLeftBank;
            this.cannOnTheLeftBank = cannOnTheLeftBank;
        }

        public int getM() {
            return m;
        }

        public int getC() {
            return c;
        }

        public boolean isBoatOnTheLeftBank() {
            return boatOnTheLeftBank;
        }

        public int getMisOnTheLeftBank() {
            return misOnTheLeftBank;
        }

        public int getCannOnTheLeftBank() {
            return cannOnTheLeftBank;
        }

        public State getParent() {
            return parent;
        }

        public void setParent(State parent) {
            this.parent = parent;
        }

        public boolean isFinalState() {
            return m == 0 && c == 0 && !boatOnTheLeftBank;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            State state = (State) o;
            return m == state.m &&
                    c == state.c &&
                    boatOnTheLeftBank == state.boatOnTheLeftBank;
        }

        @Override
        public int hashCode() {
            return Objects.hash(m, c, boatOnTheLeftBank);
        }

        @Override
        public String toString() {
            return String.format("m: %d, c: %d, boatOnTheLeftBank: %b", m, c, boatOnTheLeftBank);
        }
    }
}

使用 `State` 类来表示状态，其中 `m` 表示左岸的牧师数量，`c` 表示左岸的野人数量，`boatOnTheLeftBank` 表示船是否在左岸。同时还包括左岸的牧师数量 `misOnTheLeftBank` 和野人数量 `cannOnTheLeftBank`，以及一个指向父状态的指针。

使用 `breadthFirstSearch` 方法对状态进行广度优先搜索，查找最终状态。

使用 `getNextStates` 方法获取当前状态的所有后继状态。

在 `main` 方法中，读取用户输入的牧师和野人数量，并使用广度优先搜索查找最终状态。如果找到了最终状态，使用 `getParent` 方法从最终状态开始遍历父状态，直到回到初始状态，输出这些状态。如果没有找到最终状态，则输出“无解”。