羊、狼、农夫过河 JAVA

好的，这是一个经典的问题，我们可以采用深度优先搜索算法来解决。

首先，我们需要定义状态。状态包括河的两岸，以及现在河的哪一边。我们可以用一个三元组表示状态：(a,b,c)，其中a、b、c分别表示左岸的狼、羊、菜是否存在，true表示存在，false表示不存在；c表示农夫当前在哪一边，false表示在左岸，true表示在右岸。

接下来，我们需要定义搜索过程。我们从初始状态开始，每次选择一个合法的动作，然后转移到下一个状态。直到找到一种合法的解法或者无解为止。

动作包括：农夫自己过河，农夫带一只动物过河，农夫带两只动物过河，农夫带三只动物过河。注意，如果农夫不在岸的一侧，他不能带动物过河。

在转移状态时，需要注意以下几点：

1. 如果农夫带狼和羊过河，狼会吃掉羊，因此这种情况是不合法的。

2. 如果农夫带羊和菜过河，羊会吃掉菜，因此这种情况也是不合法的。

3. 如果已经访问过某个状态，就不需要再次访问，否则会出现死循环。

最后，我们需要输出一组合法的解法。在每次转移状态时，我们可以记录下当前的路径，当找到一组合法解法时，就可以输出路径了。

以下是Java的代码实现：

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class WolfSheepCabbage {
    private static class State {
        boolean wolf;
        boolean sheep;
        boolean cabbage;
        boolean farmer;

        public State(boolean wolf, boolean sheep, boolean cabbage, boolean farmer) {
            this.wolf = wolf;
            this.sheep = sheep;
            this.cabbage = cabbage;
            this.farmer = farmer;
        }

        public boolean isValid() {
            if (wolf && sheep && !farmer) return false;
            if (sheep && cabbage && !farmer) return false;
            return true;
        }

        public boolean isFinalState() {
            return !wolf && !sheep && !cabbage && farmer;
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(wolf ? 'W' : '-');
            sb.append(sheep ? 'S' : '-');
            sb.append(cabbage ? 'C' : '-');
            sb.append(farmer ? 'F' : '-');
            return sb.toString();
        }

        public boolean equals(Object obj) {
            if (obj == this) return true;
            if (!(obj instanceof State)) return false;
            State other = (State) obj;
            return wolf == other.wolf && sheep == other.sheep && cabbage == other.cabbage && farmer == other.farmer;
        }

        public int hashCode() {
            return (wolf ? 1 : 0) | (sheep ? 2 : 0) | (cabbage ? 4 : 0) | (farmer ? 8 : 0);
        }
    }

    private static void search() {
        Set<State> visited = new HashSet<>();
        Queue<State> queue = new LinkedList<>();
        State start = new State(true, true, true, false);
        queue.offer(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            State current = queue.poll();
            if (current.isFinalState()) {
                System.out.println("Solution found:");
                State s = current;
                while (s != null) {
                    System.out.println(s);
                    s = parents.get(s);
                }
                return;
            }
            if (current.farmer) {
                tryMove(current, new State(false, current.sheep, current.cabbage, false), visited, queue);
                tryMove(current, new State(current.wolf, false, current.cabbage, false), visited, queue);
                tryMove(current, new State(current.wolf, current.sheep, false, false), visited, queue);
                tryMove(current, new State(false, false, current.cabbage, false), visited, queue);
                tryMove(current, new State(false, current.sheep, false, false), visited, queue);
                tryMove(current, new State(current.wolf, false, false, false), visited, queue);
            } else {
                tryMove(current, new State(true, current.sheep, current.cabbage, true), visited, queue);
                tryMove(current, new State(current.wolf, true, current.cabbage, true), visited, queue);
                tryMove(current, new State(current.wolf, current.sheep, true, true), visited, queue);
                tryMove(current, new State(true, true, current.cabbage, true), visited, queue);
                tryMove(current, new State(true, current.sheep, true, true), visited, queue);
                tryMove(current, new State(current.wolf, true, true, true), visited, queue);
            }
        }
        System.out.println("No solution found!");
    }

    private static void tryMove(State current, State next, Set<State> visited, Queue<State> queue) {
        if (next.isValid() && visited.add(next)) {
            parents.put(next, current);
            queue.offer(next);
        }
    }

    private static final java.util.Map<State, State> parents = new java.util.HashMap<>();

    public static void main(String[] args) {
        search();
    }
}