本文主要是介绍农夫、狼、羊、菜过河问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
有一个农夫带一只羊、一筐菜和一只狼过河。如果没有农夫看管，则狼要吃羊，羊要吃菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？
输入描述:
题目没有任何输入。
输出描述:
题目可能有种解决方法，求出步骤最少的解决方法，
按顺序输出农夫想把羊、菜、狼全部运过河需要哪几个步骤。
如果需要将羊带过河去则输出“sheep_go”。
如果需要将羊带回来则输出“sheep_come”。
如果需要将菜带过河去则输出“vegetable_go”。
如果需要将菜带回来则输出“vegetable_come”。
如果需要将狼带过河去则输出“wolf_go”。
如果需要将狼带回来则输出“wolf_come”。
如果需要空手返回则输出“nothing_come”。
如果需要空手过河则输出“nothing_go”。
每输出一种方案，输出一行“succeed”。
分析算法
解决这个问题的关键第一步是建立初始图，第二步即是BFS遍历
建立初始图
- 用0和1表示状态问题，即0表示未过河，1表示已过河，则初始状态为0000，最终判断结束的状态为1111
- 图的顶点即为0000，0001，0011等，顶点总数为16；表示为十进制数即为0~16.
- 该为的重点是求边，求边即要把握任何物品不能被吃掉，例如从0000->1001是不存在边的，因为若农夫带菜过河，即羊会被狼吃掉。
- 状态图可以先手动分析，用于验证：
BFS遍历
由于题目要求求最短距离，则采用BFS遍历即可
code
这篇关于农夫、狼、羊、菜过河问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
