C语言关于过河问题的求大神指点啊
题目：有三个猎人带三头熊过河：其中有一头黑熊和两头棕熊！他们过河但只有一条船！已知猎人会划船 黑熊受过训练也会划船！每次只能上两熊或两人或一人一熊！如果当猎人比熊数量少的时候人就会被熊吃掉！问要怎么才能安全地带三只熊过河
#include "stdio.h"
#include"stdlib.h"
#define MaxVerNum 200 //最大顶点数
typedef enum{FALSE,TRUE}Boolean;
Boolean visited[MaxVerNum]; //对已访问的顶点标记
int path[MaxVerNum]; //保存DFS搜索到的路径，即与某顶点到下一顶点的路径
typedef struct
{
int a;
int b;
int c;
int d;
int e;
int f;
}VextexType;
typedef bool EdgeType;
typedef struct
{
VextexType vexs[MaxVerNum]; //顶点表
EdgeType edges[MaxVerNum][MaxVerNum]; //邻接矩阵，即边表
int n; //顶点数和边数
}MGraph; //MGraph是以邻接矩阵存储的图类型
int locate(MGraph *G,int A,int B,int C,int D,int E,int F) //查找顶点（R1,R2,R3,H,Z1,Z2）在顶点向量中的位置
{
int i;
for(i=0;i<G->n;i++)
if(G->vexs[i].a==A&&G->vexs[i].b==B&&G->vexs[i].c==C&&G->vexs[i].d==D&&G->vexs[i].e==E&&G->vexs[i].f==F)
return i; //返回当前位置
return -1; //没有找到此顶点
}
int is_safe(int A,int B,int C,int D,int E,int F)
{
if((A==D==E)||(A==D==F)||(A==E==F)||(A==D==E==F)||(B==D==E)||(B==D==F)||(B==E==F)||(B==D==E==F)||(C==D==E)||(C==D==F)||(C==E==F)||(C==D==E==F)||(A==B==D==E==F)||(A==C==D==E==F)||(C==B==D==E==F)) return 0; //当熊的数目多于人的时候是不安全的
else return 1;
}
int is_connected(MGraph *G,int i,int j) //判断状态i和j之间是否可以交换
{
int k=0;
if(G->vexs[i].a!=G->vexs[j].a) k++;
if(G->vexs[i].b!=G->vexs[j].b) k++;
if(G->vexs[i].c!=G->vexs[j].c) k++;
if(G->vexs[i].d!=G->vexs[j].d) k++;
if(G->vexs[i].e!=G->vexs[j].e) k++;
if(G->vexs[i].f!=G->vexs[j].f) k++;
if((G->vexs[i].a!=G->vexs[j].a)||(G->vexs[i].b!=G->vexs[j].b)||(G->vexs[i].c!=G->vexs[j].c)||(G->vexs[i].d!=G->vexs[j].d)&&k<=2)
return 1; //以上三个条件不同时满足且农夫状态改变时，返回真，即农夫每次只能带一件东西过船
else return 0;
}
void CreateG(MGraph *G)
{
int i,j,A,B,C,D,E,F;
i=0; //生成所有安全的图的顶点
for(A=0;A<=1;A++)
for(B=0;B<=1;B++)
for(C=0;C<=1;C++)
for(D=0;D<=1;D++)
for(E=0;E<=1;E++)
for(F=0;F<=1;F++)
if(is_safe(A,B,C,D,E,F))
{
G->vexs[i].a=A;
G->vexs[i].b=B;
G->vexs[i].c=C;
G->vexs[i].d=D;
G->vexs[i].e=E;
G->vexs[i].f=F;
i++;
}
G->n=i;
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
if(is_connected(G,i,j)) //状态i与j之间可以转化，初始化为1，否则为0
G->edges[i][j]=G->edges[j][i]=1;
else
G->edges[i][j]=G->edges[j][i]=0;
return ;
}
void print_path(MGraph *G,int u,int v) //输出从u到v之间的简单路径，即顶点序列中不重复的路径
{
int k,p=1;
k=u;
while(k!=v)
{
printf("第%d步:",p);
printf("\n(%d,%d,%d,%d,%d,%d)\n",G->vexs[k].a,G->vexs[k].b,G->vexs[k].c,G->vexs[k].d,G->vexs[k].e,G->vexs[k].f);
k=path[k];
p++;
}
printf("第%d步:",p);
printf("\n(%d,%d,%d,%d,%d,%d)\n",G->vexs[k].a,G->vexs[k].b,G->vexs[k].c,G->vexs[k].d,G->vexs[k].e,G->vexs[k].f);
p++;
}
void DFS_path(MGraph *G,int u,int v) //深度优先搜素从u到v的简单路径
{
int j;
visited[u]=TRUE; //标记已访问过得点
for(j=0;j<G->n;j++)
if(G->edges[u][j]&&!visited[j]&&!visited[v])
{
path[u]=j;
DFS_path(G,j,v);
}
}
void main()
{
int i,j;
MGraph graph;
CreateG(&graph);
for(i=0;i<graph.n;i++) visited[i]=FALSE; //置初值
i=locate(&graph,0,0,0,0,0,0);
j=locate(&graph,1,1,1,1,1,1);
DFS_path(&graph,i,j);
if(visited[j]) print_path(&graph,i,j);
}
图片不会插入
运行结果（手写的）:
第一步：
<-858993460,-858993460,,-858993460,-858993460,-858993460,-858993460>
Press any key to continue
运行结果不对啊，代码有些繁多，求哪位大神能指出哪里出错啦？
小弟感激不尽！
[解决办法]
传教士与野人过河问题。该算法题 360 2013校园招聘考到了。参考：
http://blog.csdn.net/huangxy10/article/details/8066408
http://bbs.csdn.net/topics/390242017
贴段代码：
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
using namespace std;
bool flag = true; //true:表示在右岸
vector<string> visit; //记录已经访问过的状态
bool dfs( int M, int C, int m, int c){
if( M<0
[解决办法]
C<0
[解决办法]
m<0
[解决办法]
c<0) //非法
return false;
if( (M&&C>M)
[解决办法]
(m&&c>m)) //野人会吃牧师
return false;
if( flag&&M==0&&C==0
[解决办法]
(!flag&&m==0&&c==0)) //全部运输过去
return true;
//检查该节点是否出现过
char s[30];
if( !flag )
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
else
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=right", m,c,M,C);
string str(s);
for( int i=0; i<visit.size(); i++)
if( visit[i]==str) //该状态已经搜索过了
return false;
visit.push_back(str);
flag = !flag;
if( dfs( m+2, c, M-2,C) ){
printf("2,0\n");
printf("%s\n",s);
return true;
}
else if( dfs( m, c+2, M, C-2) ){
printf("0,2\n");
printf("%s\n",s);
return true;
}
else if( dfs( m+1, c+1, M-1, C-1) ){
printf("1,1\n");
printf("%s\n",s);
return true;
}
else if( dfs( m+1, c, M-1, C)){
printf("1,0\n");
printf("%s\n",s);
return true;
}
else if( dfs( m, c+1, M, C-1)){
printf("0,1\n");
printf("%s\n",s);
return true;
}
flag = !flag;
visit.pop_back();
return false;
}
int main(){
char s[30];
int M=6,C=6,m=0,c=0;
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
printf("%s\n",s);
if(!dfs(M,C,0,0))
cout << "Can not find the solution."<<endl;
return 0;
}
