修道士与野人1.9.cpp

用C++实现传教士与野人问题

#include<iostream>
using namespace std;
const int maxvertices=1000;
int n;//野人或修道士的人数
int c;//小船上面最多可以容纳的人数
int x=1,y;
int result[30000][100];
//邻接边单链表的结点结构体
struct node
{
	int dest;
	node *next;
};
//数组的数据元素类型结构体
struct adjlheight
{
	int x[3];//0表示修道士,1表示野人,2表示船的状态
	int sorce;
	node *adj;
};
//邻接表结构体
struct adjlgraph
{
	adjlheight a[maxvertices];
	int numofverts;
	int numofedges;
};


//函数声明
adjinitiate(adjlgraph *g,int n,int c);//初始化
insertvertex(adjlgraph *g,int i,int x[3]);//插入结点操作
insertedge(adjlgraph *g,int v1,int v2);//插入边操作 加入边 <v1,v2> 的信息
deleteedge(adjlgraph *g,int v1,int v2);//删除边操作
int getfirstvex(adjlgraph g,int v);//取第一个邻接结点
int getnextvex(adjlgraph g,int v1,const int v2);//取下一个邻接结点
bfs(adjlgraph g,int vi);//广度优先
void dfs(adjlgraph g,int v);//深度优先





//初始化
adjinitiate(adjlgraph *g,int n,int c)
{
	int i,ci,vcount,cx,cy,vctemp,vc2;
	int boatrl;//左为1,右为0
	adjlheight temph;

	g->numofverts=0;
	g->numofedges=0;
	for(i=0;i<maxvertices;i++)
	{
		g->a[i].sorce=i;
		g->a[i].adj=NULL;
	}
	for(boatrl=1;boatrl>=0;boatrl--)
	{
		for(ci=n;ci>=0;ci--)
		{
			temph.x[0]=ci;
			temph.x[1]=ci;
			temph.x[2]=boatrl;
			insertvertex(g,g->numofverts,temph.x);
			if(ci!=n)
			{
				temph.x[0]=n;
				temph.x[1]=ci;
				temph.x[2]=boatrl;
				insertvertex(g,g->numofverts,temph.x);
			}
			if(ci==0)
			{
				for(int zzz=1;zzz<=n;zzz++)
				{
					temph.x[0]=0;
					temph.x[1]=zzz;
					temph.x[2]=boatrl;
					insertvertex(g,g->numofverts,temph.x);
				}
			}
		}
	}
	for(vcount=0;vcount<g->numofverts;vcount++)
	{
		for(cx=0;cx<=c;cx++)
		{
			for(cy=0;cy+cx<=c;cy++)
			{
				//左右
				if(g->a[vcount].x[2]==1&&(cy+cx)>0)
				{
					temph.x[0]=g->a[vcount].x[0]-cx;
					temph.x[1]=g->a[vcount].x[1]-cy;
					temph.x[2]=0;
					if(temph.x[0]==temph.x[1]&&temph.x[0]>=0&&temph.x[0]<=n)
					{
						vctemp=0;
						while(temph.x[0]!=g->a[vctemp].x[0] || temph.x[1]!=g->a[vctemp].x[1] || temph.x[2]!=g->a[vctemp].x[2])
						{
							vctemp++;
						}
						vc2=vctemp;
						insertedge(g,vcount,vc2);
					}
					if(temph.x[0]==n&&temph.x[1]<n&&temph.x[1]>=0)
					{
						vctemp=0;
						while(temph.x[0]!=g->a[vctemp].x[0] || temph.x[1]!=g->a[vctemp].x[1] || temph.x[2]!=g->a[vctemp].x[2])
						{
							vctemp++;
						}
						vc2=vctemp;
						insertedge(g,vcount,vc2);
					}
					if(temph.x[0]==0&&temph.x[1]<=n&&temph.x[1]>0)
					{
						vctemp=0;
						while(temph.x[0]!=g->a[vctemp].x[0] || temph.x[1]!=g->a[vctemp].x[1] || temph.x[2]!=g->a[vctemp].x[2])
						{
							vctemp++;
						}
						vc2=vctemp;
						insertedge(g,vcount,vc2);
					}
				}
				//右左
				if(g->a[vcount].x[2]==0&&(cx+cy)>0)
				{
					temph.x[0]=g->a[vcount].x[0]+cx;
					temph.x[1]=g->a[vcount].x[1]+cy;
					temph.x[2]=1;
					if(temph.x[0]==temph.x[1]&&temph.x[0]>=0&&temph.x[0]<=n)
					{
						vctemp=0;
						while(temph.x[0]!=g->a[vctemp].x[0] || temph.x[1]!=g->a[vctemp].x[1] || temph.x[2]!=g->a[vctemp].x[2])
						{
							vctemp++;
						}
						vc2=vctemp;
						insertedge(g,vcount,vc2);
					}
					if(temph.x[0]==n&&temph.x[1]<n&&temph.x[1]>=0)
					{
						vctemp=0;
						while(temph.x[0]!=g->a[vctemp].x[0] || temph.x[1]!=g->a[vctemp].x[1] || temph.x[2]!=g->a[vctemp].x[2])
						{
							vctemp++;
						}
						vc2=vctemp;
						insertedge(g,vcount,vc2);
					}
					if(temph.x[0]==0&&temph.x[1]<=n&&temph.x[1]>0)
					{
						vctemp=0;
						while(temph.x[0]!=g->a[vctemp].x[0] || temph.x[1]!=g->a[vctemp].x[1] || temph.x[2]!=g->a[vctemp].x[2])
						{
							vctemp++;
						}
						vc2=vctemp;
						insertedge(g,vcount,vc2);
					}
				}				
			}
		}
	}
	return 0;
}


//插入结点操作
insertvertex(adjlgraph *g,int i,int x[3])
{
	if(i>=0&&i<maxvertices)
	{
		for(int three=0;three<3;three++)
		{
			g->a[i].x[three]=x[three];
		}
		g->numofverts++;
	}
	else
		cout<<"结点越界.";
	return 0;
}


//插入边操作 加入边 <v1,v2> 的信息
insertedge(adjlgraph *g,int v1,int v2)
{
	node *p;

	if(v1<0||v1>=g->numofverts||v2<0||v2>=g->numofverts)
	{
		cout<<"参数v1或v2越界出错.";
		exit(0);
	}

	p=(node *)malloc(sizeof(node));
	p->dest=v2;

	p->next=g->a[v1].adj;
	g->a[v1].adj=p;
	g->numofedges++;

	return 0;
}


//删除边操作
deleteedge(adjlgraph *g,int v1,int v2)
{
	node *curr,*pre;

	if(v1<0||v1>=g->numofverts||v2<0||v2>=g->numofverts)
	{
		cout<<"参数越界出错.";
		exit(0);
	}
	pre=NULL;
	curr=g->a[v1].adj;
	while(curr!=NULL && curr->dest!=v2)
	{
		pre=curr;
		curr=curr->next;
	}


	if(curr!=NULL && curr->dest==v2 && pre==NULL)
	{
		g->a[v1].adj=curr->next;
		free(curr);
		g->numofedges--;
	}

	else if(curr!=NULL&&curr->dest==v2&&pre!=NULL)
	{
		pre->next=curr->next;
		free(curr);
		g->numofedges--;
	}
	else
		cout<<"边<v1,v2>不存在!";

	return 0;
}

//取第一个邻接结点
//成功返回对应序号,否则返回-1
int getfirstvex(adjlgraph g,int v)
{
	node *p;

	if(v<0||v>g.numofverts)
	{
		cout<<"参数出错.";
		exit(0);
	}

	p=g.a[v].adj;
	if(p!=NULL)
		return p->dest;
	else
		return -1;
}

//取下一个邻接结点
int getnextvex(adjlgraph g,int v1,const int v2)
{
	node *p;

	if(v1<0||v1>g.numofverts||v2<0||v2>g.numofverts)
	{
		cout<<"参数出错.";
		exit(0);
	}

	p=g.a[v1].adj;
	while(p!=NULL)
	{
		if(p->dest!=v2)
		{
			p=p->next;
			continue;
		}
		else 
			break;
	}


	p=p->next;
	if(p!=NULL)
		return p->dest;
	else 
		return -1;
}

int visited[maxvertices];
int queue[maxvertices];
int terminal[maxvertices];
int teri=1;

//深度优先
void dfs(adjlgraph g,int v)
{
	int w;
	;
	visited[v]=1;
	terminal[teri]=v;
	
	if(g.a[v].x[0]==0&&g.a[v].x[1]==0&&g.a[v].x[2]==0)
	{
		for(y=1;y<=teri;y++)
		{
			result[x][y]=terminal[y];
		}
		x++;
        visited[terminal[teri]]=0;
		teri++;
	}
	else
	{
		teri++;
		w=getfirstvex(g,v);
		while(w!=-1)
		{
			if(!visited[w])
				dfs(g,w);
			w=getnextvex(g,v,w);
		}
		visited[terminal[teri-1]]=0;
	}
	teri--;
	

}


//广度优先
bfs(adjlgraph g,int vi)
{
	teri=1;
	int front=0,rear=1,v;
	node *p;
	
	visited[vi]=1;
	queue[rear]=vi;
	terminal[teri]=vi;
	teri++;
	if(g.a[vi].x[0]==0&&g.a[vi].x[1]==0&&g.a[vi].x[2]==0)
		return 0;
	while(front!=rear)
	{
		front=(front+1)%maxvertices;
		v=queue[front];
		p=g.a[v].adj;
		while(p!=NULL)
		{
			if(visited[p->dest]==0)
			{
				visited[p->dest]=1;
				;
				rear=(rear+1)%maxvertices;
				queue[rear]=p->dest;
				terminal[teri]=p->dest;
				teri++;
				if(g.a[p->dest].x[0]==0&&g.a[p->dest].x[1]==0&&g.a[p->dest].x[2]==0)
					return 0;
			}
			p=p->next;
		}
	}
	return 0;
}



main()
{
	adjlgraph totalg;
	int i;
	cout<<"请输入修道士或者野人的人数：";
	cin>>n;
	cout<<"请输入小船能容纳的最多人数：";
	cin>>c;
	adjinitiate(&totalg,n,c);

	
	for(i=0;i<maxvertices;i++)
		visited[i]=0;
	teri=1;
	int jj,ccc[30000];
	for(int xx=0;xx<30000;xx++)
	{
		for(int yy=0;yy<100;yy++)
			result[xx][yy]=-1;
		ccc[xx]=-1;
	}
	dfs(totalg,0);
	//cout<<endl<<"深度优先"<<endl;
	for(jj=1;jj<30000&&result[jj][1]!=-1;jj++)
	{
		for(i=1;result[jj][i]!=-1;i++)
			;
		ccc[jj]=i;
	}
	if(jj==1)
		cout<<"渡河失败。";
	else
	{
		cout<<"总共有"<<jj-1<<"解。";
		ccc[0]=10000;
	 for(i=1;ccc[i]!=-1;i++)
		{
			if(ccc[i]<ccc[0])
				ccc[0]=ccc[i];
		}
		int cccount=0;
		cout<<endl<<"边数最少为"<<ccc[0]-1<<"个"<<endl;
		for(jj=1;ccc[jj]!=-1;jj++)
		{
			if(ccc[jj]==ccc[0])
			{
				for(i=1;result[jj][i]!=-1;i++)
					cout<<"("
					<<totalg.a[result[jj][i]].x[0]
					<<","
					<<totalg.a[result[jj][i]].x[1]
					<<","
					<<totalg.a[result[jj][i]].x[2]
					<<")"
					<<"  ";
				cccount++;
				cout<<endl;
			}
		}
		cout<<"边数最少的通路共有"<<cccount<<"条";
	}
	return 0;
}