问题描述 有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险。找出一种安全的渡河方法。 将该问题转变为：假如有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数（除非牧师人数为0），且假定两种人都会划船，试设计一个算法，确定它们能否渡过河去，若能，则给出一只小船来回次数最少的最佳方案。 用JAVA给我代码

以下是一个基于深度优先搜索的解决方案，可以输出最少的船来回次数：

import java.util.*;

class State {
    int m;
    int c;
    boolean boat;
    int steps;

    State(int m, int c, boolean boat, int steps) {
        this.m = m;
        this.c = c;
        this.boat = boat;
        this.steps = steps;
    }

    boolean isValid() {
        if (m < 0 || c < 0 || m > 3 || c > 3) {
            return false;
        }
        if (m > 0 && m < c) {
            return false;
        }
        if (3 - m > 0 && 3 - m < 3 - c) {
            return false;
        }
        return true;
    }

    boolean isFinal() {
        return m == 0 && c == 0 && !boat;
    }

    List<State> getNextStates() {
        List<State> nextStates = new ArrayList<>();
        if (boat) {
            // boat on right bank
            if (m >= 2) {
                nextStates.add(new State(m - 2, c, false, steps + 1));
            }
            if (c >= 2) {
                nextStates.add(new State(m, c - 2, false, steps + 1));
            }
            if (m >= 1 && c >= 1) {
                nextStates.add(new State(m - 1, c - 1, false, steps + 1));
            }
            if (m >= 1) {
                nextStates.add(new State(m - 1, c, false, steps + 1));
            }
            if (c >= 1) {
                nextStates.add(new State(m, c - 1, false, steps + 1));
            }
        } else {
            // boat on left bank
            if (m <= 1) {
                nextStates.add(new State(m + 2, c, true, steps + 1));
            }
            if (c <= 1) {
                nextStates.add(new State(m, c + 2, true, steps + 1));
            }
            if (m >= 1 && c >= 1) {
                nextStates.add(new State(m + 1, c + 1, true, steps + 1));
            }
            if (m >= 1) {
                nextStates.add(new State(m + 1, c, true, steps + 1));
            }
            if (c >= 1) {
                nextStates.add(new State(m, c + 1, true, steps + 1));
            }
        }
        return nextStates;
    }
}

public class RiverCrossing {
    public static void main(String[] args) {
        State start = new State(3, 3, true, 0);
        State end = null;

        Stack<State> stack = new Stack<>();
        Set<State> visited = new HashSet<>();

        stack.push(start);
        visited.add(start);

        while (!stack.isEmpty()) {
            State curr = stack.pop();
            if (curr.isFinal()) {
                end = curr;
                break;
            }
            List<State> nextStates = curr.getNextStates();
            for (State nextState : nextStates) {
                if (nextState.isValid() && !visited.contains(nextState)) {
                    stack.push(nextState);
                    visited.add(nextState);
                }
            }
        }

        if (end == null) {
            System.out.println("Cannot find a solution.");
        } else {
            System.out.println("Least number of boat trips: " + end.steps);
        }
    }
}

注释：

- `State` 类表示状态，包含当前岸上的牧师和野人人数、船的位置以及已经用的船来回次数。
- `isValid()` 方法判断状态是否合法，即是否满足题目中的要求。
- `isFinal()` 方法判断状态是否为目标状态，即所有人都在对岸且船在对岸。
- `getNextStates()` 方法返回所有合法的下一步状态。
- 主函数使用深度优先搜索寻找最少的船来回次数。