分享自己做的 7-5 课后作业

Question

• 判断状态是否合法：如果 狼和羊、羊和菜 在同一河岸的情况下，农夫必须和他们在一边才行，否则不行；其他情况都是可以的
• 下一个状态：农夫带一个和它在同一河岸的物件过河，当然，只带自己是可以的（什么都不带）

golang 实现：

import "fmt"

func solveProblem2() {
	const (
		S_A_SIDE    = '0' // 在河岸一边
		S_B_SIDE    = '1' // 在河岸另一边
		I_WOLF      = 0   // 数组中狼的 idx
		I_SHEEP     = 1   // 数组中羊的 idx
		I_VEGETABLE = 2   // 数组中菜的 idx
		I_FARMER    = 3   // 数组中农夫的 idx
	)
	var (
		// 狼 羊 菜 农夫
		initStatus = []byte{S_A_SIDE, S_A_SIDE, S_A_SIDE, S_A_SIDE}

		// 如果狼和羊、羊和菜在同一河岸的情况下，必须农夫和他们在一边才行，否则不行
		// 其他情况都是可以的
		cango = func(status []byte) bool {
			if status[I_WOLF] == status[I_SHEEP] {
				return status[I_FARMER] == status[I_SHEEP]
			}
			if status[I_SHEEP] == status[I_VEGETABLE] {
				return status[I_FARMER] == status[I_SHEEP]
			}
			return true
		}
		finish = func(status []byte) bool {
			return status[I_WOLF] == S_B_SIDE &&
				status[I_SHEEP] == S_B_SIDE &&
				status[I_VEGETABLE] == S_B_SIDE &&
				status[I_FARMER] == S_B_SIDE
		}
		toggleStatus = func(status byte) byte { return S_A_SIDE + S_B_SIDE - status }

		// 下一个状态：农夫带一个和它在同一河岸的物件过河，
		// 当然，只带自己是可以的（什么都不带）
		nextStatus = func(status []byte) (result [][]byte) {
			farmerStatus := status[I_FARMER]
			for idx, v := range status {
				if v == farmerStatus {
					ns := make([]byte, len(initStatus))
					copy(ns, status)
					ns[idx] = toggleStatus(v)
					ns[I_FARMER] = toggleStatus(v)
					result = append(result, ns)
				}
			}
			return
		}

		preStatusMap = make(map[string]string)
		queue        []string
	)

	preStatusMap[string(initStatus)] = string(initStatus)
	queue = append(queue, string(initStatus))

LOOP:
	for len(queue) > 0 {
		s := []byte(queue[0])
		queue = queue[1:]
		nextStatuses := nextStatus(s)
		for _, ns := range nextStatuses {
			if cango(ns) {
				if _, ok := preStatusMap[string(ns)]; !ok {
					preStatusMap[string(ns)] = string(s)
					if finish(ns) {
						break LOOP
					}
					queue = append(queue, string(ns))
				}
			}
		}
	}

	fs := string([]byte{S_B_SIDE, S_B_SIDE, S_B_SIDE, S_B_SIDE})

	for fs != string(initStatus) {
		fmt.Println(fs)
		if _, ok := preStatusMap[fs]; !ok {
			panic("failed to get result")
		}
		fs = preStatusMap[fs]
	}
	fmt.Println(fs)
}

输出应该为其中的一个解，0 代表在初始的河岸，1 代表在目标的河岸，序列分别代表：狼、羊、菜、农夫 的状态

1111
1010
1011
1000
1101
0100
0101
0000

Answer 1

liuyubobobo 2020-04-07 13:48:48

大赞！感谢分享！：）

继续加油！：）

• 提问者 Schwarzeni #1

  :-)

Answer 2

jandy_chen 2020-10-01 22:17:57

//补充java版本了
public class NonFu7_5 {
    private String[] pre;//1代表出现在目的地，0代表不出现在目的地；第1位代表农夫，第2位代表狼，第3位代表羊，第4位代表菜。
    private String start="0000";//目标地初始为0000,代表还未开始要过河；
    private String end="1111";//目标地为1111依次代表农夫，狼，羊，菜过河了。

    public NonFu7_5(){
        Queue<String> q=new LinkedList<>();
        boolean[] visied=new boolean[16]; //开一个够大的空间
        pre=new String[16];

        q.add(start);
        visied[0]=true;
        while (!q.isEmpty()){
            String cur=q.remove();

            //可以达到的状态
            ArrayList<String> nexts=getNexts(cur);
            for(String next:nexts){
                if(!visied[Str2Int(next)]){
                    q.add(next);
                    visied[Str2Int(next)]=true;
                    pre[Str2Int(next)]=cur;

                    if(next.equals(end)){
                        return;
                    }
                }
            }
        }
    }

    //将字符串转二进制，在转换成int
    private int Str2Int(String str){
        char[] chars=str.toCharArray();
        int out=0;
        for(int i=0;i<chars.length;i++){
            out +=(chars[chars.length-1-i]-'0')<<i;
        }
        return out;
    }

    //取原始地，状态
    private String getOppStr(String str){
        char[] chars=str.toCharArray();
        StringBuffer out=new StringBuffer();
        for(int i=0;i<chars.length;i++){
            out.append(chars[i]=='1'?'0':'1');
        }
        return out.toString();
    }



    //获取下一轮个可能的状态
    // 农夫每次运一个种类过河，或者自己过河
    // 农夫确保目的地，及原始地，不能让狼和羊，或者羊和菜单独留着，也就不能存在 0110（狼吃羊），0011（羊吃菜）,0111(狼吃羊,或者羊吃菜）
    private ArrayList<String> getNexts(String curs){
        ArrayList<String> nexts=new ArrayList<>();
        char[] chars=curs.toCharArray();
        StringBuffer next=new StringBuffer();

        //自己过河
        for(int i=0;i<chars.length;i++){
            if(i==0){
                next.append(chars[i]=='1'?'0':'1');
            } else{
                next.append(chars[i]);
            }

        }
        if(checkTarget(next.toString()) && checkOrig(next.toString())){
            nexts.add(next.toString());
        }

        //自己过河+运其中一个过河
        for(int j=1;j<chars.length;j++){
            next=new StringBuffer();
            for(int i=0;i<chars.length;i++){
                if(i==0){
                    next.append(chars[i]=='1'?'0':'1');
                } else{
                    if(i==j){
                        next.append(chars[i]=='1'?'0':'1');
                    } else{
                        next.append(chars[i]);
                    }

                }

            }
            if(checkTarget(next.toString()) && checkOrig(next.toString())){
                nexts.add(next.toString());
            }
        }

        return nexts;

    }
    private boolean checkTarget(String str){
       if("0110".equals(str)){
           return false; //0110（狼吃羊）
       } else if("0011".equals(str)){
           return false;//0011（羊吃菜）
       } else if("0111".equals(str)){
           return false;//0111(狼吃羊,或者羊吃菜）
       } else{
           return true;
       }
    }

    private boolean checkOrig(String str){
        String ss=getOppStr(str);
        return checkTarget(ss);
    }

    public Iterable<String> result(){
        ArrayList<String> res=new ArrayList<>();

        String curs=end;
        while (!curs.equals(start)){
            res.add(curs);
            curs=pre[Str2Int(curs)];
        }
        res.add(start);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        System.out.println((new NonFu7_5()).result());
        // 输出：[0000, 1010, 0010, 1110, 0100, 1101, 0101, 1111]
    }

}

• liuyubobobo #1

  大赞！感谢分享！：）