用Java编写过河问题：问题转变为：假如有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数（除非牧师人数为0），且假定两种人都会划船，试设计一个算法，确定它们能否渡过河去，若能，则给出一只小船来回次数最少的最佳方案。

以下是用Java编写的河问题的解法：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RiverCrossing {

    private static final int NUM_OF_PASSENGERS = 3; // 每次最多能过河的人数
    private static final int NUM_OF_PASSENGERS_TYPE = 2; // 人的种类数量（牧师和野人）
    private static final int NUM_OF_BOAT_SEATS = 2; // 小船可以坐的人数
    private static final int START_STATE = 0; // 起始状态
    private static final int END_STATE = (1 << (NUM_OF_PASSENGERS * NUM_OF_PASSENGERS_TYPE)) - 1; // 终止状态

    private static final int LEFT_BANK = 0; // 左岸
    private static final int RIGHT_BANK = 1; // 右岸

    private static final int MISSIONARY = 0; // 牧师
    private static final int CANNIBAL = 1; // 野人

    // 判断当前状态是否合法
    private static boolean isValid(int state) {
        int leftBank[] = decodeState(state, LEFT_BANK);
        int rightBank[] = decodeState(state, RIGHT_BANK);
        if (leftBank[MISSIONARY] != 0 && leftBank[MISSIONARY] < leftBank[CANNIBAL])
            return false;
        if (rightBank[MISSIONARY] != 0 && rightBank[MISSIONARY] < rightBank[CANNIBAL])
            return false;
        return true;
    }

    // 将状态转换为数组
    private static int[] decodeState(int state, int bank) {
        int[] bankArray = new int[NUM_OF_PASSENGERS_TYPE];
        for (int i = 0; i < NUM_OF_PASSENGERS; i++) {
            int passengerType = (state >> (i * NUM_OF_PASSENGERS_TYPE + bank * NUM_OF_PASSENGERS_TYPE * NUM_OF_PASSENGERS))
                    & (NUM_OF_PASSENGERS_TYPE - 1);
            bankArray[passengerType]++;
        }
        return bankArray;
    }

    // 将数组转换为状态
    private static int encodeState(int[] leftBank, int[] rightBank) {
        int state = 0;
        for (int i = 0; i < NUM_OF_PASSENGERS; i++) {
            state |= (leftBank[MISSIONARY] > i ? MISSIONARY : CANNIBAL)
                    << (i * NUM_OF_PASSENGERS_TYPE + LEFT_BANK * NUM_OF_PASSENGERS_TYPE * NUM_OF_PASSENGERS);
            state |= (rightBank[MISSIONARY] > i ? MISSIONARY : CANNIBAL)
                    << (i * NUM_OF_PASSENGERS_TYPE + RIGHT_BANK * NUM_OF_PASSENGERS_TYPE * NUM_OF_PASSENGERS);
        }
        return state;
    }

    // 判断状态是否是终止状态
    private static boolean isEndState(int state) {
        return state == END_STATE;
    }

    // 判断两个状态是否相等
    private static boolean isEqual(int state1, int state2) {
        return state1 == state2;
    }

    // 判断一个状态是否已经被访问过
    private static boolean isVisited(int state, Set<Integer> visitedStates) {
        return visitedStates.contains(state);
    }

    // 获取下一个可能的状态
    private static List<Integer> getNextPossibleStates(int state) {
        List<Integer> nextPossibleStates = new ArrayList<>();
        int[] leftBank = decodeState(state, LEFT_BANK);
        int[] rightBank = decodeState(state, RIGHT_BANK);
        int boatPosition = LEFT_BANK;
        if (leftBank[NUM_OF_PASSENGERS_TYPE - 1] == NUM_OF_PASSENGERS
                && isEndState(encodeState(rightBank, leftBank))) {
            nextPossibleStates.add(encodeState(leftBank, rightBank));
            return nextPossibleStates;
        }
        if (rightBank[NUM_OF_PASSENGERS_TYPE - 1] == NUM_OF_PASSENGERS
                && isEndState(encodeState(leftBank, rightBank))) {
            nextPossibleStates.add(encodeState(leftBank, rightBank));
            return nextPossibleStates;
        }
        if (leftBank[MISSIONARY] >= 1 && boatPosition == LEFT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newLeftBank[MISSIONARY]--;
            newRightBank[MISSIONARY]++;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (leftBank[CANNIBAL] >= 1 && boatPosition == LEFT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newLeftBank[CANNIBAL]--;
            newRightBank[CANNIBAL]++;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (leftBank[MISSIONARY] >= 2 && boatPosition == LEFT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newLeftBank[MISSIONARY] -= 2;
            newRightBank[MISSIONARY] += 2;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (leftBank[CANNIBAL] >= 2 && boatPosition == LEFT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newLeftBank[CANNIBAL] -= 2;
            newRightBank[CANNIBAL] += 2;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (leftBank[MISSIONARY] >= 1 && leftBank[CANNIBAL] >= 1 && boatPosition == LEFT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newLeftBank[MISSIONARY]--;
            newLeftBank[CANNIBAL]--;
            newRightBank[MISSIONARY]++;
            newRightBank[CANNIBAL]++;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (rightBank[MISSIONARY] >= 1 && boatPosition == RIGHT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newRightBank[MISSIONARY]--;
            newLeftBank[MISSIONARY]++;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (rightBank[CANNIBAL] >= 1 && boatPosition == RIGHT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newRightBank[CANNIBAL]--;
            newLeftBank[CANNIBAL]++;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (rightBank[MISSIONARY] >= 2 && boatPosition == RIGHT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newRightBank[MISSIONARY] -= 2;
            newLeftBank[MISSIONARY] += 2;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (rightBank[CANNIBAL] >= 2 && boatPosition == RIGHT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newRightBank[CANNIBAL] -= 2;
            newLeftBank[CANNIBAL] += 2;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        if (rightBank[MISSIONARY] >= 1 && rightBank[CANNIBAL] >= 1 && boatPosition == RIGHT_BANK) {
            int[] newLeftBank = leftBank.clone();
            int[] newRightBank = rightBank.clone();
            newRightBank[MISSIONARY]--;
            newRightBank[CANNIBAL]--;
            newLeftBank[MISSIONARY]++;
            newLeftBank[CANNIBAL]++;
            if (isValid(encodeState(newLeftBank, newRightBank)))
                nextPossibleStates.add(encodeState(newLeftBank, newRightBank));
        }
        return nextPossibleStates;
    }

    // 搜索最短路径
    private static List<Integer> search() {
        List<Integer> shortestPath = new ArrayList<>();
        Set<Integer> visitedStates = new HashSet<>();
        List<List<Integer>> paths = new ArrayList<>();
        List<Integer> startPath = new ArrayList<>();
        startPath.add(START_STATE);
        paths.add(startPath);

        while (!paths.isEmpty()) {
            List<Integer> currentPath = paths.remove(0);
            int currentState = currentPath.get(currentPath.size() - 1);
            if (isEndState(currentState)) {
                if (shortestPath.isEmpty() || currentPath.size() < shortestPath.size())
                    shortestPath = currentPath;
                continue;
            }
            visitedStates.add(currentState);
            List<Integer> nextPossibleStates = getNextPossibleStates(currentState);
            for (int nextState : nextPossibleStates) {
                if (isVisited(nextState, visitedStates))
                    continue;
                List<Integer> nextPath = new ArrayList<>(currentPath);
                nextPath.add(nextState);
                paths.add(nextPath);
            }
        }
        return shortestPath;
    }

    // 打印结果
    private static void printResult(List<Integer> path) {
        System.out.println("Number of boat trips: " + (path.size() - 1));
        for (int i = 0; i < path.size() - 1; i++) {
            int[] leftBank = decodeState(path.get(i), LEFT_BANK);
            int[] rightBank = decodeState(path.get(i), RIGHT_BANK);
            int[] nextLeftBank = decodeState(path.get(i + 1), LEFT_BANK);
            int[] nextRightBank = decodeState(path.get(i + 1), RIGHT_BANK);

            System.out.println("From left bank to right bank: ");
            System.out.println("Missionaries: " + (leftBank[MISSIONARY] - nextLeftBank[MISSIONARY]));
            System.out.println("Cannibals: " + (leftBank[CANNIBAL] - nextLeftBank[CANNIBAL]));

            System.out.println("From right bank to left bank: ");
            System.out.println("Missionaries: " + (rightBank[MISSIONARY] - nextRightBank[MISSIONARY]));
            System.out.println("Cannibals: " + (rightBank[CANNIBAL] - nextRightBank[CANNIBAL]));
        }
    }

    public static void main(String[] args) {
        List<Integer> path = search();
        printResult(path);
    }
}

该程序将所有可能的状态表示为一个二进制数，并使用两个数组来表示左岸和右岸上的每种人的数量。搜索算法使用BFS，并利用isValid，encodeState和decodeState函数来处理状态。getNextPossibleStates函数返回下一组可能的状态。程序搜索最短路径，然后打印出每次小船的行动。