首页 > 代码库 > 修道士与野人问题(BFS广度搜索)
修道士与野人问题(BFS广度搜索)
#include "iostream.h" #include "string.h" //定义一个状态节点 typedef struct //存储各个状态 { int x,y,s;//修道士人数,野人人数,s=0左岸s=1右岸 }state; typedef struct edge { int verNo;//顶点号; int x_boat,y_boat,di;//船上修道士人数,船上野人人数,方向,di=1向右,di=0向左 struct edge* next; }edge; typedef struct { state st; edge *e; }vert; typedef struct { vert ver[1000] ; int vNum; }adjGraph; typedef struct { int pos;//pos为该状态在邻接表的顶点表中的位置 int pre;//pre指的是队中当前元素前驱在qu.dt中的位置 }data; typedef struct { data dt[1000]; int front,rear; }Queue; //创建顶点表,并记录所有状态的个数adj.vNum void CreteAllState(adjGraph &adj,int m,int n) { for (int c1=0;c1<=1;c1++) for(int m1=0;m1<=m;m1++) for (int n1=0;n1<=n&&n1<=m1||m1==0&&n1<=n;n1++)//野人要少于修道士人数或全是野人 { adj.ver[adj.vNum].st.s=c1; adj.ver[adj.vNum].st.x=m1; adj.ver[adj.vNum].st.y=n1; adj.ver[adj.vNum].e=NULL; cout<<c1<<‘\t‘<<m1<<‘\t‘<<n1<<‘\t‘<<adj.vNum<<endl; adj.vNum++; } } //在顶点表中查找状态位置(下标) int SearchState(adjGraph adj,state st) { for (int i=0;i<adj.vNum;i++) if(st.s==adj.ver[i].st.s && st.x==adj.ver[i].st.x && st.y==adj.ver[i].st.y) return i; return -1; } int CheckState(adjGraph adj,state st,int m,int n)//判断st状态是否可作为第i状态的后续状态,如果是则返回后续状态的位置,否则返回-1; { int pos;state st_OtherSide; st_OtherSide.s=st.s==1?0:1; st_OtherSide.x=m-st.x; st_OtherSide.y=n-st.y; pos=SearchState(adj,st_OtherSide); if(pos==-1) return -1; pos=SearchState(adj,st); if(pos==-1) return -1; return pos; } //创建边表 void CreateEdges(adjGraph &adj,int m,int n,int c) { edge *t;state st;int j,k,vNo; for(int i=0;i<adj.vNum;i++) { if (adj.ver[i].st.x+adj.ver[i].st.y>0)//修道士与野人总数大于0 { if(adj.ver[i].st.y>0)//假如船上全部为野人 for (j=1;j<=adj.ver[i].st.y&&j<=c;j++) { st.s=adj.ver[i].st.s==1?0:1; st.x=m-adj.ver[i].st.x; st.y=n-(adj.ver[i].st.y-j); vNo=CheckState(adj,st,m,n); if(vNo==-1) continue; //非法状态则跳过 t=new edge;//左岸就往右岸的状态转变 t->verNo=vNo;t->di=st.s;t->x_boat=0;t->y_boat=j; t->next=adj.ver[i].e;//头插法 adj.ver[i].e=t; } if(adj.ver[i].st.x>1)//船上有j个修道士与k个野人 for (j=1;j<=adj.ver[i].st.x&&j<=c;j++)// for (k=0;k<=c-j&&k<=adj.ver[i].st.y;k++) { st.s=adj.ver[i].st.s==1?0:1; st.x=m-(adj.ver[i].st.x-j); st.y=n-(adj.ver[i].st.y-k); vNo=CheckState(adj,st,m,n); if(vNo==-1) continue;//非法状态则跳过 t=new edge;//右岸就往左岸的状态转变 t->verNo=vNo;t->di=st.s;t->x_boat=j;t->y_boat=k; t->next=adj.ver[i].e;//头插法 adj.ver[i].e=t; } } } } void Disp(adjGraph adj) { edge *e; for (int i=0;i<adj.vNum;i++) { cout<<i<<‘\t‘; cout<<adj.ver[i].st.s<<‘\t‘; cout<<adj.ver[i].st.x<<‘\t‘; cout<<adj.ver[i].st.y<<‘\t‘; e=adj.ver[i].e; cout<<endl; while (e) { cout<<‘\t‘<<"顶点号"<<‘\t‘<<"方向"<<‘\t‘<<"船上修道士"<<‘\t‘<<"船上野人"<<endl; cout<<‘\t‘<<e->verNo<<‘\t‘<<e->di<<‘\t‘<<e->x_boat<<‘\t‘<<e->y_boat<<endl; e=e->next; } cout<<endl; } } void PrintPath1(adjGraph &adj,Queue &qu,int i)//由i向前找路 { if (qu.dt[i].pre!=-1) PrintPath1(adj,qu,qu.dt[i].pre); int k=qu.dt[i].pos; cout<<i<<‘\t‘; cout<<adj.ver[k].st.s<<‘\t‘; cout<<adj.ver[k].st.x<<‘\t‘; cout<<adj.ver[k].st.y<<‘\t‘; cout<<endl; } void PrintPath(adjGraph &adj,Queue &qu,int i)//由i向前找路 { for (int k=0;k<=i;k++) { cout<<k<<‘\t‘; cout<<qu.dt[k].pos<<‘\t‘; cout<<qu.dt[k].pre<<‘\t‘; cout<<endl; } } void BreadthSearch(adjGraph adj,int* visit,Queue &qu,int x,int y) { int stPos,finPos,tag=1; qu.front=qu.rear=-1; state st,fin; st.s=0;st.x=x;st.y=y; stPos=CheckState(adj,st,x,y); if(stPos==-1) cout<<"start position error!"<<endl; fin.s=1;fin.x=x;fin.y=y; finPos=SearchState(adj,fin); qu.rear++; qu.dt[qu.rear].pos=stPos;//起始位置入队 qu.dt[qu.rear].pre=-1;//pre指的是队中当前元素前驱在qu.dt中的位置 while(qu.rear!=qu.front&&tag) { qu.front++;//出队一元素 visit[qu.dt[qu.front].pos]=1; if (qu.dt[qu.front].pos==finPos) { tag=0; cout<<"find the path!"<<endl; PrintPath1(adj,qu,qu.front); //插入打印路径的函数 break; } edge *e; e=adj.ver[qu.dt[qu.front].pos].e;//e points to the first adjacent edge; while (e) { if(visit[e->verNo]==0) { qu.dt[++qu.rear].pos=e->verNo; qu.dt[qu.rear].pre=qu.front; } e=e->next; } } if(tag==1) cout<<"cant find the path!"<<endl; } void main() { int m,n,c;//修道士人数,野人人数,船上最多可载人数 adjGraph adj;Queue qu; adj.vNum=0; cin>>m>>n>>c; CreteAllState(adj,m,n); CreateEdges(adj,m,n,c); Disp(adj); int visit[1000]; memset(visit,0,sizeof(visit));//把数组置空 BreadthSearch(adj,visit,qu,m,n); }
去掉调试代码:
#include "iostream.h" #include "string.h" //定义一个状态节点 typedef struct //存储各个状态 { int x,y,s;//修道士人数,野人人数,s=0左岸s=1右岸 }state; typedef struct edge { int verNo;//顶点号; int x_boat,y_boat,di;//船上修道士人数,船上野人人数,方向,di=1向右,di=0向左 struct edge* next; }edge; typedef struct { state st; edge *e; }vert; typedef struct { vert ver[1000] ; int vNum; }adjGraph; typedef struct { int pos;//pos为该状态在邻接表的顶点表中的位置 int pre;//pre指的是队中当前元素前驱在qu.dt中的位置 }data; typedef struct { data dt[1000]; int front,rear; }Queue; //创建顶点表,并记录所有状态的个数adj.vNum void CreteAllState(adjGraph &adj,int m,int n) { for (int c1=0;c1<=1;c1++) for(int m1=0;m1<=m;m1++) for (int n1=0;n1<=n&&n1<=m1||m1==0&&n1<=n;n1++)//野人要少于修道士人数或全是野人 { adj.ver[adj.vNum].st.s=c1; adj.ver[adj.vNum].st.x=m1; adj.ver[adj.vNum].st.y=n1; adj.ver[adj.vNum].e=NULL; cout<<c1<<‘\t‘<<m1<<‘\t‘<<n1<<‘\t‘<<adj.vNum<<endl; adj.vNum++; } } //在顶点表中查找状态位置(下标) int SearchState(adjGraph adj,state st) { for (int i=0;i<adj.vNum;i++) if(st.s==adj.ver[i].st.s && st.x==adj.ver[i].st.x && st.y==adj.ver[i].st.y) return i; return -1; } int CheckState(adjGraph adj,state st,int m,int n)//判断st状态是否可作为第i状态的后续状态,如果是则返回后续状态的位置,否则返回-1; { int pos;state st_OtherSide; st_OtherSide.s=st.s==1?0:1; st_OtherSide.x=m-st.x; st_OtherSide.y=n-st.y; pos=SearchState(adj,st_OtherSide); if(pos==-1) return -1; pos=SearchState(adj,st); if(pos==-1) return -1; return pos; } //创建边表 void CreateEdges(adjGraph &adj,int m,int n,int c) { edge *t;state st;int j,k,vNo; for(int i=0;i<adj.vNum;i++) { if (adj.ver[i].st.x+adj.ver[i].st.y>0)//修道士与野人总数大于0 { if(adj.ver[i].st.y>0)//假如船上全部为野人 for (j=1;j<=adj.ver[i].st.y&&j<=c;j++) { st.s=adj.ver[i].st.s==1?0:1; st.x=m-adj.ver[i].st.x; st.y=n-(adj.ver[i].st.y-j); vNo=CheckState(adj,st,m,n); if(vNo==-1) continue; //非法状态则跳过 t=new edge;//左岸就往右岸的状态转变 t->verNo=vNo;t->di=st.s;t->x_boat=0;t->y_boat=j; t->next=adj.ver[i].e;//头插法 adj.ver[i].e=t; } if(adj.ver[i].st.x>1)//船上有j个修道士与k个野人 for (j=1;j<=adj.ver[i].st.x&&j<=c;j++)// for (k=0;k<=c-j&&k<=adj.ver[i].st.y;k++) { st.s=adj.ver[i].st.s==1?0:1; st.x=m-(adj.ver[i].st.x-j); st.y=n-(adj.ver[i].st.y-k); vNo=CheckState(adj,st,m,n); if(vNo==-1) continue;//非法状态则跳过 t=new edge;//右岸就往左岸的状态转变 t->verNo=vNo;t->di=st.s;t->x_boat=j;t->y_boat=k; t->next=adj.ver[i].e;//头插法 adj.ver[i].e=t; } } } } void PrintPath1(adjGraph &adj,Queue &qu,int i)//由i向前找路 { if (qu.dt[i].pre!=-1) PrintPath1(adj,qu,qu.dt[i].pre); int k=qu.dt[i].pos; cout<<i<<‘\t‘; cout<<adj.ver[k].st.s<<‘\t‘; cout<<adj.ver[k].st.x<<‘\t‘; cout<<adj.ver[k].st.y<<‘\t‘; cout<<endl; } void BreadthSearch(adjGraph adj,int* visit,Queue &qu,int x,int y) { int stPos,finPos,tag=1; qu.front=qu.rear=-1; state st,fin; st.s=0;st.x=x;st.y=y; stPos=CheckState(adj,st,x,y); if(stPos==-1) cout<<"start position error!"<<endl; fin.s=1;fin.x=x;fin.y=y; finPos=SearchState(adj,fin); qu.rear++; qu.dt[qu.rear].pos=stPos;//起始位置入队 qu.dt[qu.rear].pre=-1;//pre指的是队中当前元素前驱在qu.dt中的位置 while(qu.rear!=qu.front&&tag) { qu.front++;//出队一元素 visit[qu.dt[qu.front].pos]=1; if (qu.dt[qu.front].pos==finPos) { tag=0; cout<<"find the path!"<<endl; PrintPath1(adj,qu,qu.front); //插入打印路径的函数 break; } edge *e; e=adj.ver[qu.dt[qu.front].pos].e;//e points to the first adjacent edge; while (e) { if(visit[e->verNo]==0) { qu.dt[++qu.rear].pos=e->verNo; qu.dt[qu.rear].pre=qu.front; } e=e->next; } } if(tag==1) cout<<"cant find the path!"<<endl; } void main() { int m,n,c;//修道士人数,野人人数,船上最多可载人数 adjGraph adj;Queue qu; adj.vNum=0; cin>>m>>n>>c; CreteAllState(adj,m,n); CreateEdges(adj,m,n,c); Disp(adj); int visit[1000]; memset(visit,0,sizeof(visit));//把数组置空 BreadthSearch(adj,visit,qu,m,n); }
修道士与野人问题(BFS广度搜索)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。