学步园

/*<br /> 三个野人，三个牧师过河问题，要求任意时刻野人人数不能多于牧师的人数。<br /> <span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>：<br /> 广搜穷举。A*不知道怎样写。。。<br /> 程序实现了选择走最少次数的一个解，并不是所有的可行解。<br /> */<br /> #include<iostream><br /> #include<deque><br /> #include<algorithm><br /> using namespace std;<br /> struct point{<br /> int a,b,s,f;//a,表示出发岸牧师的人数，b表示野人的人数，对岸的人数可以通过简单的运算得到。 s表示当前是在岸的那边，0表示在出发岸，1表示在对岸；f表示父节点的位置<br /> point(int a,int b,int s,int f):a(a),b(b),s(s),f(f){}<br /> };<br /> deque<point> dq;//广搜队列；<br /> bool operator==(const point& p1,const point& p2){return p1.a==p2.a&&p1.b==p2.b&&p1.s==p2.s;}<br /> ostream& operator<<(ostream& _os,const point& p){//输出状态<br /> return _os<<"["<<p.a<<","<<p.b<<","<<p.s<<","<<p.f<<"]";<br /> }<br /> bool ishave(int a,int b,int s){//判断当前状态是否出现过<br /> if(find(dq.begin(),dq.end(),point(a,b,s,0))!=dq.end())return 1;<br /> return 0;<br /> }<br /> bool isgo(int a,int b,int s)//用来判断时候可以过去<br /> {<br /> if(s==0){<br /> if(a<0||b<0||a>3||b>3)return 0;<br /> if(a!=0&&a<b)return 0;<br /> return 1;<br /> }else{<br /> int a1=3-a,b1=3-b;<br /> if(a1<0||b1<0||a1>3||b1>3)return 0;<br /> if(a1!=0&&a1<b1)return 0;<br /> return 1;<br /> }<br /> }<br /> //显示一条移动最少次数的路径<br /> void show(int pos)<br /> {<br /> if(dq[pos].f==pos){<br /> cout<<dq[pos]<<endl;<br /> return;<br /> }<br /> show(dq[pos].f);<br /> cout<<dq[pos]<<endl;<br /> }<br /> int main()<br /> {<br /> int a=3,b=3,s;<br /> int pos=0;//当前节点的位置<br /> dq.push_back(point(a,b,0,0));<br /> while(pos!=dq.size()){//当还有元素可以加入的时候加入循环<br /> a=dq[pos].a;<br /> b=dq[pos].b;<br /> s=dq[pos].s;<br /> if(a==0&&b==0&&s==1)break;<br /> if(dq[pos].s==0){//出发，5种情况列举<br /> if(a<b&&a!=0){pos++;continue;}//状态不可用<br /> if(isgo(a,b-2,0)&&!ishave(a,b-2,1))<br /> dq.push_back(point(a,b-2,1,pos));<br /> if(isgo(a-2,b,0)&&!ishave(a-2,b,1))<br /> dq.push_back(point(a-2,b,1,pos));<br /> if(isgo(a-1,b-1,0)&&!ishave(a-1,b-1,1))<br /> dq.push_back(point(a-1,b-1,1,pos));<br /> if(isgo(a-1,b,0)&&!ishave(a-1,b,1))<br /> dq.push_back(point(a-1,b,1,pos));<br /> if(isgo(a,b-1,0)&&!ishave(a,b-1,1))<br /> dq.push_back(point(a,b-1,1,pos));<br /> }else{//回来<br /> if((3-a)!=0&&(3-a)<(3-b)){pos++;continue;}//状态不可用<br /> if(isgo(a+2,b,1)&&!ishave(a+2,b,0))<br /> dq.push_back(point(a+2,b,0,pos));<br /> if(isgo(a,b+2,1)&&!ishave(a,b+2,0))<br /> dq.push_back(point(a,b+2,0,pos));<br /> if(isgo(a+1,b+1,1)&&!ishave(a+1,b+1,0))<br /> dq.push_back(point(a+1,b+1,0,pos));<br /> if(isgo(a+1,b,1)&&!ishave(a+1,b,0))<br /> dq.push_back(point(a+1,b,0,pos));<br /> if(isgo(a,b+1,1)&&!ishave(a,b+1,0))<br /> dq.push_back(point(a,b+1,0,pos));<br /> }<br /> pos++;<br /> }<br /> /*队列状态*/<br /> for(int i=0;i<dq.size();i++)<br /> cout<<i<<": "<<dq[i]<<endl;<br /> //显示一条最优路径<br /> cout<<"----------------------"<<endl;<br /> show(pos);<br /> }