农夫过河（基于C语言）

一位农夫、一只狼、一只羊和一颗白菜都在河的一侧，他们想到河的另一侧。河中有一条船，一次只能载农夫和一个物体（狼或羊或白菜）。若农夫不在的时候，狼会吃掉羊，羊会吃掉白菜。问：该以什么样的方式才能将狼、羊和白菜完好的运到对岸？

  我们不妨假设河是南北走向，河的东侧记为0，西侧记为1，fwsc（即：农夫farmer、狼wolf、羊sheep和白菜cabbage，下文都以fwsc的形式表示）都在河的东侧（河岸0），他们要乘船去往河对岸（河岸1）。   人脑逻辑思路为：① 农夫把羊运到河岸1；② 农夫回来河岸0；③ 把白菜运往河岸1；④ 把羊运到河岸0；⑤ 把狼运到河岸1；⑥ 再回来河岸0；⑦ 把羊运往河岸1；即完成运输，当然还有另一种方法，这里不再介绍。   那么说了这么多，我想表达的是，在上面的逻辑中，农夫的每一次往返过程都是类似的，即流程是一样的，那么我们可不可以用一个名为过程的函数来表示这一系列的往返过程，然后只需要判断农夫与wsc中的任一个动或物过河时，剩下的动或物能否和平共存即可。

① 首先，我们可以定义一个一组枚举变变量（预定义也可以）。 ② 这里要讲一下：我们可以假设在河岸过河为 1，没过河为 0，这里是按照二进制的格式赋值的，例如 8 = 1000，4 = 0100，2 = 0010，1 = 0001，这四种格式都代表fwsc在河岸1时的状态。

① 在这里先说名currentLocation的含义，笔者认为是每一次农夫移动前后各个物体的位置分布情况，例如：1010 表示：农夫在河岸1，狼在河岸0，羊在河岸1，白菜在河岸0，也就是十进制的10。注意：currentLocation不会大于16。 ② 下面涉及到2进制运算，假设当前位置为 0000，即初始位置（因为fwsc都在河岸的东侧），那么假设判断农夫在哪，即 0000 & 1000 = 0000，就可以得到农夫在河东侧；currentLocation & 1000 结果只有两种可能，要么为 0（0000），要么为 8（1000）。

① 这里就是判断当前的位置状态是否安全，即当农夫不在的情况下，判断：狼是否和羊在一起；羊是否和白菜在一起。用0表示不安全，1表示安全。

① 该过程涉及到数据结构的广度优先遍历和深度优先遍历，这里笔者就不再讲述，各位看官可以自行百度，或者参考最下面的参考文章。 ② 我们起初用的都是2进制的设定，而且初始位置分布情况为 0（0000），最终位置分布情况为 15（1111），所以我们要设定一个包含16个元素的数组，来表示各个位置分布状态；并且用 -1代表该状态未被执行过，因为农夫先把羊运往河岸1，此时的位置分布状态为：1010，若农夫再把羊运回来（即 0000），则没有任何意义，并且还会导致程序无限循环。 ③ 数组的值为前驱值，即上一个位置分布状态的值，例如：route[10(1010)]=0(0000)，即农夫在一开始将羊运往对岸的过程。注：初始状态的前驱值为 -2，表示其上一个状态不存在。 笔者曾经困惑的地方： ① mover int mover; //代表移动的哪个物体 for (mover = 1; mover int nextLocation = currentLocation ^ (farmer | mover); //预先得出下一状态 if (isSafe(nextLocation) && route[nextLocation] == -1) //判断下一状态是否安全，并且下一状态是否进行过了。 { int nextRoute[16]; //这里再次建立路径数组是因为路径有多种可能，而一条路径数组只代表一种可能 for (int i = 0; i //若返回值等于0，则表示该物体在河的东侧，即河岸0；若返回值等于1，则表示该物体在河岸西侧，即河岸1. switch (fwsc) { case cabbage: if ((currentLocation & cabbage) == 0) //2进制与运算，判断物体是否在河岸1，若在不在河岸1，则结果为0。 return 0; else return 1; break; case sheep: if ((currentLocation & sheep) == 0) return 0; else return 1; break; case wolf: if ((currentLocation & wolf) == 0) return 0; else return 1; break; case farmer: if ((currentLocation & farmer) == 0) return 0; else return 1; break; default: break; } return -1; } int isSafe(int currentLocation) //返回0，表示不安全；返回1，表示安全。 { int f, w, s, c; f = getLocation(currentLocation, farmer); w = getLocation(currentLocation, wolf); s = getLocation(currentLocation, sheep); c = getLocation(currentLocation, cabbage); if (f != w && w == s) //若农夫不和狼在一侧，而狼却和羊在一侧 return 0; else if (f != s && s == c) //若农夫不和羊在一侧，而羊却和白菜在一侧 return 0; return 1; } int printRoute(int route[16], int status) { if (status == 0) { printf("初始状态：农夫、狼、羊和白菜都在河的一侧。\n"); return 1; } printRoute(route, route[status]); char s[200] = ""; if ((route[status] & cabbage) == cabbage) strcat(s, "白菜在河岸1。"); else strcat(s, "白菜在河岸0。"); if ((route[status] & sheep) == sheep) strcat(s, "羊在河岸1。"); else strcat(s, "羊在河岸0。"); if ((route[status] & wolf) == wolf) strcat(s, "狼在河岸1。"); else strcat(s, "狼在河岸0。"); if ((route[status] & farmer) == farmer) strcat(s, "农夫在河岸1。"); else strcat(s, "农夫在河岸0。"); printf("%s\n", s); return 1; } int process(int route[16], int currentLocation) //农夫运送过程(核心) { if (route[15] == -1) //最终状态 1111（十进制15），即fwsc都在河对岸 { int mover; //代表移动的哪个物体 for (mover = 1; mover int nextLocation = currentLocation ^ (farmer | mover); //预先得出下一状态 if (isSafe(nextLocation) && route[nextLocation] == -1) //判断下一状态是否安全，并且下一状态是否进行过了。 { int nextRoute[16]; //这里再次建立路径数组是因为路径有多种可能，而一条路径数组只代表一种可能 for (int i = 0; i -2 }, currentLocation = 0; for (int i = 1; i