车羊问题c语言编程 C语言-人狼羊菜问题-最容易看懂的解决方法及代码

题目描述：农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。

想这个问题一连想了好几天，本人没有系统的学过算法，有些概念也不是很清楚，只因解决问题为目标。

尝试过图论解决，但用floyed算法只能算出最短路径值，如何输出过程，一直没想出好的解决方法。

然后看了下面这篇文章，尝试抛弃图论，用树的思想来解决这个问题。建议阅读下面代码时，先看看这篇文章。

参考资料：/orbit/article/details/7563220

在写代码时，本人采用了上述文章中的思想，又借鉴了图论中存储结点的一些方法。

我觉得这样写应该非常容易看懂了。具体思路见代码。

1 #include

2 #define INF 9999

3 //8个动作

4 char *action[8]={"农夫单独过河","农夫带狼过河","农夫带羊过河","农夫带菜过河",

5 "农夫单独返回","农夫带狼返回","农夫带羊返回","农夫带菜返回"};

6 //10种状态

7 char *state[10]={"人狼羊菜","人狼羊","人狼菜","人羊菜","人羊","狼菜","狼","羊","菜","空"};

8

9 //状态转换规则：GA[i][j]=k 表示【状态i】可以通过【动作k】转换到【状态j】，GA[i][j]=INF表示不可直接转换

10 int GA[10][10]={INF,INF,INF,INF,INF, 2,INF,INF,INF,INF,

11 INF,INF,INF,INF,INF,INF, 2, 1,INF,INF,

12 INF,INF,INF,INF,INF, 0, 3,INF, 1,INF,

13 INF,INF,INF,INF,INF,INF,INF, 3, 2,INF,

14 INF,INF,INF,INF,INF,INF,INF, 0,INF, 2,

15 6,INF, 4,INF,INF,INF,INF,INF,INF,INF,

16 INF, 6, 7,INF,INF,INF,INF,INF,INF,INF,

17 INF, 5,INF, 7, 4,INF,INF,INF,INF,INF,

18 INF,INF, 5, 6,INF,INF,INF,INF,INF,INF,

19 INF,INF,INF,INF, 6,INF,INF,INF,INF,INF};

20

21 //记录每一步的动作

22 int record_action[20];

23 //记录每一步动作后的状态

24 int record_state[20];

25

26 //搜索从第step步开始、第i个结点到第n个结点的过程(step从0算起)

27 void search(int i,int n,int step)

28 {

29 int k;//动作

30 int j;//可能要转换到的状态

31 if(i==n)

32 {

33 for(k=0;k

34 printf("step %d: %s，左岸还剩 %s\n",k+1,action[record_action[k]],state[record_state[k]]);

35 printf("step count:%d\n\n",step);

36 return;

37 }

38 //查找在当前【状态i】下能转换到的【其它状态j】，并且【状态j】不能在之前出现过

39 //查找时可能会出现多个 j，所以这是一个多叉树

40 for(k=0;k<8;k++)

41 {

42 for(j=0;j<10;j++)

43 if(GA[i][j]!=INF&&GA[i][j]==k)//判断状态i能否通过动作k转换到状态j

44 {

45 int m;

46 //下面这个循环是判断状态j在之前是否出现过

47 for(m=0;m

48 if(j==record_state[m])break;

49 if(m

50 //如果j满足前面所有条件，则记录这一步

51 record_action[step]=k; //第step步所使用的动作

52 record_state[step]=j; //第step步所转换的状态

53 search(j,n,step+1); //继续搜索下一步

54 }

55 }

56

57 }

58 int main()

59 {

60 search(0,9,0);

61 return 0;

62 }

来源：/zandbin/p/5341656.html