狼羊菜过河一次运一样怎么过

需要向对岸运四次。第一次把羊运过河；第二次把狼运过河，回来时把羊运回；第三次把菜运过河；第四次把羊再运过河。一个农夫有一条船，和狼、羊、菜，农夫要把这3样东西运到河到另一边，农夫每次最多只能通过这个船运一样东西，要防止狼吃羊、羊吃白菜（即不能在没有农夫在的情况下同时在同一岸边）因此运送的顺序至关重要。答案一：农夫带羊过河。农夫返回。农夫带狼过河。农夫带羊返回。农夫带菜过河。农夫返回。农夫带羊过河。<结束>再看一个答案：农夫带羊过河。农夫返回。农夫带菜过河。农夫带羊返回。农夫带狼过河。农夫返回。农夫带羊过河。<结束>扩展资料：过河问题实现：问题抽象：建立一个struct型的state，其中包括4个bool型的变量a1 a2 a3 a4分别对应人、狼、羊、菜的状态，值为true代表在起始的河岸边，false代表在对岸，起始时4个分量都为true。农夫每过一次河生成一个新的state。根据题目可知，农夫过一次河a1取反，且a2 a3 a4值与a1相同的分量也可以分别取反分别生成一个新的state代表被农夫运到河的对岸的各种选择。只有a1取反而a2 a3 a4都没取反生成的新状态代表农夫自己过河没有带东西。每次生成一个新状态后，首先要检查是否达到了终止状态（a1 a2 a3 a4都为false），其次要检查是否是合法状态（要同时考虑一个state对应的河两岸是否有狼吃羊、羊吃白菜的情况出现），如果状态合法。没到终止状态且没有在广度遍历队列中出现过，则将状态插入广度遍历队列，否则将该状态丢弃。在此过程中我们没有考虑正在渡河的情况，因为每次过河船上总是有人，不会出现冲突，视其为不稳定状态直接忽略。