农夫过河问题java

农夫过河问题是一个经典的人工智能问题，它可以用来展示搜索算法的应用。问题描述如下：一个农夫要带着一只狼、一只羊和一些青菜过河，但是小船只能装下农夫和另外一样物品，如果农夫不在场，狼会吃羊，羊会吃青菜。请问农夫如何才能安全地将这些物品全部运到对岸？

解决这个问题的方法是使用深度优先搜索或广度优先搜索算法。具体实现可以参考以下Java代码：

import java.util.*;

public class FarmerCrossRiver {
    private static final int FARMER = 0;
    private static final int WOLF = 1;
    private static final int SHEEP = 2;
    private static final int VEGETABLES = 3;

    private static final int LEFT = 0;
    private static final int RIGHT = 1;

    private static final int[][] MOVE = {
            {WOLF, SHEEP},
            {SHEEP},
            {SHEEP, VEGETABLES},
            {VEGETABLES}
    };

    private static final String[] MOVE_NAME = {
            "wolf and sheep",
            "sheep",
            "sheep and vegetables",
            "vegetables"
    };

    private static final String[] SIDE_NAME = {
            "left",
            "right"
    };

    private static final int[] INITIAL_STATE = {LEFT, LEFT, LEFT, LEFT};
    private static final int[] FINAL_STATE = {RIGHT, RIGHT, RIGHT, RIGHT};

    private static boolean isSafe(int[] state) {
        if (state[WOLF] == state[SHEEP] && state[FARMER] != state[WOLF]) {
            return false;
        }
        if (state[SHEEP] == state[VEGETABLES] && state[FARMER] != state[SHEEP]) {
            return false;
        }
        return true;
    }

    private static boolean isFinal(int[] state) {
        return Arrays.equals(state, FINAL_STATE);
    }

    private static void printState(int[] state) {
        System.out.print("farmer is on the " + SIDE_NAME[state[FARMER]] + ", ");
        System.out.print("wolf is on the " + SIDE_NAME[state[WOLF]] + ", ");
        System.out.print("sheep is on the " + SIDE_NAME[state[SHEEP]] + ", ");
        System.out.println("vegetables is on the " + SIDE_NAME[state[VEGETABLES]]);
    }

    private static void printSolution(List<int[]> path) {
        for (int i = 0; i < path.size(); i++) {
            int[] state = path.get(i);
            if (i == 0) {
                System.out.println("Initial state:");
            } else {
                System.out.println("Move " + MOVE_NAME[state[FARMER]]);
            }
            printState(state);
        }
        System.out.println("Final state:");
        printState(FINAL_STATE);
    }

    public static void main(String[] args) {
        Stack<int[]> stack = new Stack<>();
        Set<String> visited = new HashSet<>();
        stack.push(INITIAL_STATE);
        visited.add(Arrays.toString(INITIAL_STATE));
        while (!stack.isEmpty()) {
            int[] state = stack.pop();
            if (isFinal(state)) {
                List<int[]> path = new ArrayList<>();
                while (state != null) {
                    path.add(state);
                    state = (int[]) state[4];
                }
                Collections.reverse(path);
                printSolution(path);
                break;
            }
            for (int i = 0; i < MOVE.length; i++) {
                int[] newState = Arrays.copyOf(state, state.length);
                newState[FARMER] = 1 - newState[FARMER];
                for (int j = 0; j < MOVE[i].length; j++) {
                    int item = MOVE[i][j];
                    if (newState[item] != newState[FARMER]) {
                        newState[item] = 1 - newState[item];
                    }
                }
                if (isSafe(newState) && !visited.contains(Arrays.toString(newState))) {
                    visited.add(Arrays.toString(newState));
                    newState[4] = state;
                    stack.push(newState);
                }
            }
        }
    }
}