农夫、狼、羊、菜过河问题

Question

import java.util.*;
import java.util.stream.Collectors;

/**
 * 农夫、狼、羊、菜过河问题：
 * 只有农夫能划船，除农夫外每次只能运一种东西，
 * 如果没有农夫看着，羊会吃菜，狼会吃羊，
 * 求全部运到河对岸的方式
 */
public class CrossRiverPuzzle {
    private int[] pre;
    private boolean[] visited;

    public CrossRiverPuzzle() {
        visited = new boolean[10000];
        pre = new int[10000];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        pre[0] = 0;

        while (!queue.isEmpty()) {
            int cur = queue.remove();
            int farmer = cur / 1000, wolf = cur % 1000 / 100, lamb = cur % 100 / 10, cab = cur % 10;

            ArrayList<Integer> nexts = new ArrayList<>();
            // 农夫自己过
            nexts.add(crossed(farmer) * 1000 + wolf * 100 + lamb * 10 + cab);
            // 农夫、狼，只能运和自己在一边的
            if (farmer == wolf)
                nexts.add(crossed(farmer) * 1000 + crossed(wolf) * 100 + lamb * 10 + cab);
            // 农夫、羊
            if (farmer == lamb)
                nexts.add(crossed(farmer) * 1000 + wolf * 100 + crossed(lamb) * 10 + cab);
            // 农夫、菜
            if (farmer == cab)
                nexts.add(crossed(farmer) * 1000 + wolf * 100 + lamb * 10 + crossed(cab));

            for (int next : nexts) {
                int farmerN = next / 1000, wolfN = next % 1000 / 100, lambN = next % 100 / 10, cabN = next % 10;
                // 没有访问过，且狼不能吃羊、羊不能吃菜
                if (!visited[next] && save(farmerN, wolfN, lambN) && save(farmerN, lambN, cabN)) {
                    queue.add(next);
                    visited[next] = true;
                    pre[next] = cur;
                }

                if (next == 1111)
                    return;
            }
        }
    }

    public Iterable<Integer> result() {
        ArrayList<Integer> res = new ArrayList<>();
        if (!visited[1111])
            return res;

        int cur = 1111;
        while (cur != 0) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(0);
        Collections.reverse(res);

        return res;
    }

    private boolean save(int farmer, int strong, int weak) {
        return strong != weak || farmer == strong;
    }

    // 过河，将1转0,0转1
    private int crossed(int v) {
        return 1 - v;
    }

    public static void main(String[] args) {
        for (int cur: (new CrossRiverPuzzle()).result()) {
            System.out.println((new CrossRiverPuzzle()).convertCur(cur));
        }
    }

    public String convertCur(int cur) {
        int farmer = cur / 1000, wolf = cur % 1000 / 100, lamb = cur % 100 / 10, cab = cur % 10;
        Map<String, Integer> map = new HashMap<>();
        map.put("农夫", farmer);
        map.put("狼", wolf);
        map.put("羊", lamb);
        map.put("菜", cab);

        StringBuilder sb = new StringBuilder();
        sb.append("河边：");
        List<String> list = map.keySet().stream().filter(i -> map.get(i) == 0).collect(Collectors.toList());
        for (String s : list) {
            sb.append(s);
            sb.append(" ");
        }
        sb.append("\n");
        sb.append("岸边：");
        list = map.keySet().stream().filter(i -> map.get(i) == 1).collect(Collectors.toList());
        for (String s : list) {
            sb.append(s);
            sb.append(" ");
        }
        sb.append("\n");
        return sb.toString();
    }
}

运行结果是：

河边：农夫 羊 狼 菜 
岸边：

河边：狼 菜 
岸边：农夫 羊 

河边：农夫 狼 菜 
岸边：羊 

河边：菜 
岸边：农夫 羊 狼 

河边：农夫 羊 菜 
岸边：狼 

河边：羊 
岸边：农夫 狼 菜 

河边：农夫 羊 
岸边：狼 菜 

河边：
岸边：农夫 羊 狼 菜 

Answer 1

liuyubobobo 2024-10-19 09:57:28

大赞！感谢分享！：）

• 提问者 爱喝水的阿水 #1

  bobo老师，最近还会有新课嘛

• liuyubobobo 回复 提问者 爱喝水的阿水 #2

  近期没有新课的打算。以后应该还会有哒，感谢支持啦！：）