问题是这样的
一个农夫带着一匹狼、一只羊、一颗白菜要过河，只有一条船而且农夫每次最多只能带一个动物或物品过河，并且当农夫不在的时候狼会吃羊，羊会吃白菜，列出所有安全将所有动物和物品带过河的方案
上代码
先说解决方法很多，什么遍历绝对是可以的。但是我钟意的是用图来解决，不过也发现了另一个有意思的方法。
#include<stdio.h>
#include<string.h>
/*0表示农民的开始位置，1表示对岸*/
int famerLocation(int currentLocation) //判断农民的位置
{
if((currentLocation&8)==8)
{
return 1;
}
else
{
return 0;
}
}
int wolfLocation(int currentLocaiton) //判断狼的位置
{
if((currentLocaiton&4)==4)
{
return 1;
}
else
{
return 0;
}
}
int goatLocation(int currentLocation) //判断羊的位置
{
if((currentLocation&2)==2)
{
return 1;
}
else
{
return 0;
}
}
int cabbageLocation(int currentLocation) //判断白菜的位置
{
if((currentLocation&1)==1)
{
return 1;
}
else
{
return 0;
}
}
int judgeSafe(int currentLocation) //判断当前状态是否安全
{ //安全返回1，不安全返回0
int a,b,c,d;
a=famerLocation(currentLocation);
b=wolfLocation(currentLocation);
c=goatLocation(currentLocation);
d=cabbageLocation(currentLocation);
if(a!=b&&b==c) //当农夫和狼位置不同而狼和羊位置相同时不安全
{
return 0;
}
else if((a!=c)&&(c==d)) //当农夫和羊位置不同而羊和白菜位置相同时不安全
{
return 0;
}
else
{
return 1;
}
}
/*这里我修改了一下*/
void printRoute(int route[16]) //根据一个路径数组输出一条路径
{
int location=15;
char status[16][50] = {"空","白菜","羊","羊和白菜"
,"狼","狼和白菜","狼和羊","狼羊和白菜"
,"农夫","农夫和白菜","农夫和羊","农夫羊和白菜"
,"农夫和狼","农夫狼和白菜","农夫狼和羊","农夫狼羊和白菜"};
while(location!=-2)
{
printf("原岸：%s, 对岸：%s", status[location], status[15-location]);
location=route[location];
printf("\n");
}
printf("\n");
}
void process(int route[16],int currentLocation) //算法核心，输入要处理的路径route[16]和该路径当前最新位置currentLocation
{
if(route[15]==-1) //如果该路径还未到达目的状态
{
int mover;
for(mover=1;mover<=8;mover<<=1) //依次带不同的动物或单独过河过河4种方案
{
if(((currentLocation&8)!=0)==((currentLocation&mover)!=0)) //如果农夫和要带的动或物在同一侧
{
int nextLocation=currentLocation^(8|mover); //用异或运算表示出过河后的状态
if(judgeSafe(nextLocation)&&route[nextLocation]==-1) //判断下一个状态是否安全并且是否产生重复
{
int nextRoute[16],i;
for(i=0;i<16;i++) //用一个新的数组先拷贝当前的路径
{
nextRoute[i]=route[i];
}
nextRoute[nextLocation]=currentLocation; //然后再记录下这新的一步
process(nextRoute,nextLocation); //用递归（深度优先搜索）再以同样方式处理这个新的路径和最新位置
}
}
}
}
else //该路径到达了目标状态
{
printRoute(route); //输出该路径
}
}
int main(){
int route[16];
int i;
for(i=1;i<16;i++) //初始化路径，未经历的状态记录-1
{
route[i]=-1;
}
route[0]=-2; //起始状态已经经历过且没有前驱节点记录为-2
process(route,0); //处理该条起始路径即可
}
解释一下，代码不是我本人的，而是来自SeanMiao95，我修改了部分
我钟意的图
#include<iostream>
#include <stdlib.h>
using namespace std;
#define VertexNum 16 //最大顶点数
typedef struct // 图的顶点
{
int farmer; // 农夫
int wolf; // 狼
int sheep; //羊
int veget; // 白菜
}Vertex;
typedef struct
{
int vertexNum; // 图的当前顶点数
Vertex vertex[VertexNum]; // 顶点向量（代表顶点）
bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关
}AdjGraph;// 定义图的邻接矩阵存储结构
bool visited[VertexNum] = { false }; // 对已访问的顶点进行标记（图的遍历）
int retPath[VertexNum] = { -1 }; // 保存DFS搜索到的路径，即与某顶点到下一顶点的路径
// 查找顶点（F，W，S，V）在顶点向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)
{
for (int i = 0; i < graph->vertexNum; i++) // 从0开始查找
{
if (graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf&& graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget)
{
return i; //返回顶点序号i,start=0,end=9
}
}
return -1; //没有找到此顶点
}
// 判断目前的（F，W，S，V）是否安全
bool isSafe(int farmer, int wolf, int sheep, int veget) //当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的
{
if (farmer != sheep && (wolf == sheep || sheep == veget))
{
return false;
}
else
{
return true; // 安全返回true
}
}
// 判断状态i与状态j之间是否可转换
bool isConnect(AdjGraph *graph, int i, int j)
{
int k = 0;
if (graph->vertex[i].wolf != graph->vertex[j].wolf)
{
k++;
}
if (graph->vertex[i].sheep != graph->vertex[j].sheep)
{
k++;
}
if (graph->vertex[i].veget != graph->vertex[j].veget)
{
k++;
}
// 以上三个条件不同时满足两个且农夫状态改变时，返回真,也即农夫每次只能带一件东西过河或者不带东西过河
if (graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1)
{
return true;
}
else
{
return false;
}
}
// 创建连接图
void CreateG(AdjGraph *graph)
{
int i = 0;
int j = 0;
// 生成所有安全的图的顶点
for (int farmer = 0; farmer <= 1; farmer++)
{
for (int wolf = 0; wolf <= 1; wolf++)
{
for (int sheep = 0; sheep <= 1; sheep++)
{
for (int veget = 0; veget <= 1; veget++)
{
if (isSafe(farmer, wolf, sheep, veget))
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
graph->vertex[i].veget = veget;
i++;
}
}
}
}
}
// 邻接矩阵初始化即建立邻接矩阵
graph->vertexNum = i;//把产生的10组安全组合赋给vertexNum
for (i = 0; i < graph->vertexNum; i++)
{
for (j = i; j < graph->vertexNum; j++)
{
// 状态i与状态j之间可转化，初始化为1，否则为0
if (isConnect(graph, i, j))//农夫状态必须改变，其他三个只能改变一个，只能带一个过河
{
graph->Edge[i][j] = graph->Edge[j][i] = true;
}
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 输出从u到v的简单路径，即顶点序列中不重复出现的路径
void printPath(AdjGraph *graph, int start, int end)
{
char status[16][50] = {"空","白菜","羊","羊和白菜"
,"狼","狼和白菜","狼和羊","狼羊和白菜"
,"农夫","农夫和白菜","农夫和羊","农夫羊和白菜"
,"农夫和狼","农夫狼和白菜","农夫狼和羊","农夫狼羊和白菜"};
int i=0;
while(retPath[i] != 0)
{
printf("原岸：%s, 对岸：%s", status[retPath[i]], status[15-retPath[i]]);
i=retPath[i];
printf("\n");
}
printf("\n");
}
// 深度优先搜索从u到v的简单路径//DFS--Depth First Search
void dfsPath(AdjGraph *graph, int start, int end)
{
int i = 0;
visited[start] = true;//标记已访问过的顶点
if (start == end)
{
return;
}
for (i = 0; i < graph->vertexNum; i++)
{
if (graph->Edge[start][i] && !visited[i])//保证在所有路径里，并且没有被遍历过
{
retPath[start] = i;//把刚遍历的顶点作为起始顶点，继续往后遍历
dfsPath(graph, i, end);
}
}
}
int main()
{
AdjGraph graph;
CreateG(&graph);
int start = locate(&graph, 0, 0, 0, 0);//start=0
int end = locate(&graph, 1, 1, 1, 1);//end=9
dfsPath(&graph, start, end);
if (visited[end])
{
printPath(&graph, start, end);
system("pause");
return 0;
}
}
解释一下，代码不是我本人的，而是来自欧阳磊，我修改了部分
这里再说一下图的方法，下面是我画的一个示意图
可以看到，2的位置和7的位置分别分叉了，然后使用深度优先遍历时，先走的是2-6（因为i从0到graph->vertexNum递增的），然后到了7走7-3。这里便利的时候把2-8-3的路径给当作了不合适的路径，而且还标志了“已遍历”。所以结果出来的（retPath[]）只有0-5-2-6-1-7-4-9一条路径
版权声明：本文为zhuiQiuMX原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。