/*

三个野人，三个牧师过河问题，要求任意时刻野人人数不能多于牧师的人数。

算法：

广搜穷举。A*不知道怎样写。。。

程序实现了选择走最少次数的一个解，并不是所有的可行解。

*/

#include

#include

#include

using namespace std;

struct point{

int a,b,s,f;//a,表示出发岸牧师的人数，b表示野人的人数，对岸的人数可以通过简单的运算得到。 s表示当前是在岸的那边，0表示在出发岸，1表示在对岸；f表示父节点的位置

point(int a,int b,int s,int f):a(a),b(b),s(s),f(f){}

};

deque dq;//广搜队列；

bool operator==(const point& p1,const point& p2){return p1.a==p2.a&&p1.b==p2.b&&p1.s==p2.s;}

ostream& operator<

return _os<

}

bool ishave(int a,int b,int s){//判断当前状态是否出现过

if(find(dq.begin(),dq.end(),point(a,b,s,0))!=dq.end())return 1;

return 0;

}

bool isgo(int a,int b,int s)//用来判断时候可以过去

{

if(s==0){

if(a<0||b<0||a>3||b>3)return 0;

if(a!=0&&a

return 1;

}else{

int a1=3-a,b1=3-b;

if(a1<0||b1<0||a1>3||b1>3)return 0;

if(a1!=0&&a1

return 1;

}

}

//显示一条移动最少次数的路径

void show(int pos)

{

if(dq[pos].f==pos){

cout<

return;

}

show(dq[pos].f);

cout<

}

int main()

{

int a=3,b=3,s;

int pos=0;//当前节点的位置

dq.push_back(point(a,b,0,0));

while(pos!=dq.size()){//当还有元素可以加入的时候加入循环

a=dq[pos].a;

b=dq[pos].b;

s=dq[pos].s;

if(a==0&&b==0&&s==1)break;

if(dq[pos].s==0){//出发，5种情况列举

if(a

if(isgo(a,b-2,0)&&!ishave(a,b-2,1))

dq.push_back(point(a,b-2,1,pos));

if(isgo(a-2,b,0)&&!ishave(a-2,b,1))

dq.push_back(point(a-2,b,1,pos));

if(isgo(a-1,b-1,0)&&!ishave(a-1,b-1,1))

dq.push_back(point(a-1,b-1,1,pos));

if(isgo(a-1,b,0)&&!ishave(a-1,b,1))

dq.push_back(point(a-1,b,1,pos));

if(isgo(a,b-1,0)&&!ishave(a,b-1,1))

dq.push_back(point(a,b-1,1,pos));

}else{//回来

if((3-a)!=0&&(3-a)

if(isgo(a+2,b,1)&&!ishave(a+2,b,0))

dq.push_back(point(a+2,b,0,pos));

if(isgo(a,b+2,1)&&!ishave(a,b+2,0))

dq.push_back(point(a,b+2,0,pos));

if(isgo(a+1,b+1,1)&&!ishave(a+1,b+1,0))

dq.push_back(point(a+1,b+1,0,pos));

if(isgo(a+1,b,1)&&!ishave(a+1,b,0))

dq.push_back(point(a+1,b,0,pos));

if(isgo(a,b+1,1)&&!ishave(a,b+1,0))

dq.push_back(point(a,b+1,0,pos));

}

pos++;

}

/*队列状态*/

for(int i=0;i

cout<

//显示一条最优路径

cout<

show(pos);

}