请稍等 ...

分享一个自己写的，关于7-5课后作业(使用状态标记实现智力题：农夫/羊/狼/菜的运输问题)

代码模仿了转盘锁的写法，使用deadEnd数组标记羊狼一岸，羊菜一岸的特殊情况

import java.util.*;

public class BearLoad {
    //使用一个长度为4的字符串表示状态，0位表示农夫，1位表示羊，2位表示狼，3位表示菜
    static final String initial = "0000";
    static final String target = "1111";
    String[] deadEnd = {"0111", "0110", "1001", "1000", "0101", "1010"};
    private HashMap<String, String> visited;//visited中的key值存储当前状态，value值存储上一个状态

    public BearLoad(){

        visited = new HashMap<>();
        for(String str: deadEnd)
            visited.put(str, "");//对于deadEnd的情况，我们事先将其放入visited中，保证后面一定不会遍历到
        
        //bfs过程
        Queue<String> queue = new LinkedList<>();
        queue.add(initial);
        visited.put(initial, initial);
        while(!queue.isEmpty()){
            String cur = queue.remove();

            //获得nexts数组(相邻节点)
            ArrayList<String> nexts = new ArrayList<>();
            char farmer = cur.charAt(0);
            for(int i = 0; i < cur.length(); i ++) {
                StringBuilder sb = new StringBuilder(cur);
                sb.setCharAt(0, Character.forDigit(1 - (farmer - 48), 10));
                if(i == 0)//可以农夫自己一个人过岸
                    nexts.add(sb.toString());
                else if(cur.charAt(i) == farmer){//如果 羊/狼/菜 跟农夫在同一岸，则农夫可以改变他们的状态
                    sb.setCharAt(i, Character.forDigit(1 - (farmer - 48), 10));
                    nexts.add(sb.toString());
                }
            }
            //遍历相邻节点
            for(String next: nexts)
                if(!visited.containsKey(next)){
                    queue.add(next);
                    visited.put(next, cur);
                    if(next.equals(target))
                        return;
                }
        }
    }

    public Iterable<String> solution(){
        ArrayList<String> res = new ArrayList<>();
        String cur = target;
        while(!cur.equals(initial)){
            res.add(cur);
            cur = visited.get(cur);
        }
        res.add(initial);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args){
        System.out.println((new BearLoad()).solution());
    }
}

martin123_ 2019-09-21 13:31:02

源自：7-5 代码实现一道智力题

900

收起