4、猎人问题 一个猎人带着一只狼、一头羊和一筐青菜欲乘一独木舟渡河，因独木舟太小，猎人一次至多只能带狼、羊或青菜之一渡河，但当与猎人不在河的同一边时，狼会吃掉羊、羊会吃掉青菜。试设计一个算法，帮猎人寻找一种渡河的次序让其不受损失地将狼、羊和青菜带过河去？java代码

以下是一个简单的 Java 代码实现，使用深度优先搜索算法来解决问题：

import java.util.*;

public class HunterProblem {
    static final int WOLF = 0;
    static final int SHEEP = 1;
    static final int VEGETABLES = 2;
    
    static final int[] LEFT_BANK = {1, 1, 1};
    static final int[] RIGHT_BANK = {0, 0, 0};
    
    static final int BOAT_CAPACITY = 1;
    
    static final int[][] MOVES = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    
    static boolean isValid(int[] bank) {
        // 检查是否有羊和青菜在一起，或者狼和羊在一起
        if ((bank[SHEEP] == 1 && bank[VEGETABLES] == 1) || (bank[WOLF] == 1 && bank[SHEEP] == 1)) {
            return false;
        }
        return true;
    }
    
    static boolean isGoal(int[] bank) {
        return Arrays.equals(bank, RIGHT_BANK);
    }
    
    static void dfs(int[] bank, Set<String> visited, List<String> path) {
        if (isGoal(bank)) {
            System.out.println(path);
            return;
        }
        
        for (int i = 0; i < MOVES.length; i++) {
            int[] newBank = bank.clone();
            newBank[BOAT_CAPACITY] = bank[BOAT_CAPACITY] ^ 1;
            for (int j = 0; j < newBank.length - 1; j++) {
                newBank[j] += MOVES[i][j];
            }
            
            if (isValid(newBank) && !visited.contains(Arrays.toString(newBank))) {
                visited.add(Arrays.toString(newBank));
                path.add(Arrays.toString(newBank));
                dfs(newBank, visited, path);
                path.remove(path.size() - 1);
            }
        }
    }
    
    public static void main(String[] args) {
        int[] initialBank = LEFT_BANK.clone();
        Set<String> visited = new HashSet<>();
        visited.add(Arrays.toString(initialBank));
        List<String> path = new ArrayList<>();
        path.add(Arrays.toString(initialBank));
        dfs(initialBank, visited, path);
    }
}

在这个代码中，我们使用一个 int 数组表示左岸和右岸的情况。0 表示狼，1 表示羊，2 表示青菜，3 表示船只。

我们使用深度优先搜索算法来检查所有可能的情况，并找到一种满足条件的渡河方案。我们使用一个 Set 来记录已经访问过的状态，以避免重复搜索。我们还使用一个 List 来记录搜索路径，以便最终输出结果。

在搜索时，我们对每个状态都尝试四种可能的移动方式：将狼、羊或青菜中的一个带到对岸，或者将船只返回原岸。我们检查每个状态是否有效（即没有羊和青菜在一起，或者狼和羊在一起），并且是否已经访问过。如果是一个有效的状态并且没有访问过，我们将其添加到已访问集合中，并且继续搜索下一步。如果我们找到了一种满足条件的渡河方案，我们就输出搜索路径。