mc.cpp

野人修道士问题C++源代码

#include "mc.h"
Node::Node()
{
}
Node::~Node()
{
}
int Node::Gn()
{
	return n_step;
}
int Node::Hn()
{
	return n_m+n_c-2*n_b;
}
int Node::Fn()
{
	return Node::Gn()+Node::Hn();
}

int main()
{
	Node* p_openHead;   
    Node* p_closeHead;  
    Node* p_openFirst;      
    Node* p_getOpenFirst;      
    Node* p_closeFirst;    
    
    Node* p_newNodeOfInsertOpen;      
    Node* p_openCompare;      
    Node* p_closeCompare;     
    Node* p_closePrintFather;     
    Node* p_closePrintSon;     
    Node* p_beforeOpenNewInsert;      

    int n_tempM;        
    int n_tempC;        
    int n_tempB;        
	int n_tempStep;
    int n_tempSelfNumber;      
    int n_tempFatherNumber;    
    int n_autoAddNumber=1;     //从close中扩展到open时，给生成的节点selfnumber记数
    int i,j;                   
    int n_safe=0;              //生命野人吃人(是：0,否:1)
    int n_openCompare=0;       //open中是否有新扩展节点（有：1,无：0)
    int n_closeCompare=0;      //close中是否有新扩展节点（有：1,无：0)
    
    //创建open和close
    p_openHead=new Node;
    p_openHead->p_next=NULL;
    p_closeHead=new Node;
    p_closeHead->p_next=NULL;

    //创建初始节点，加到open中
	p_openFirst=new Node;
    p_openFirst->n_m=3;
    p_openFirst->n_c=3;
    p_openFirst->n_b=1;
    p_openFirst->n_selfNumber=1;
    p_openFirst->n_fatherNumber=0;
	p_openFirst->n_step=0;

    p_openFirst->p_next=p_openHead->p_next;//null
    p_openHead->p_next=p_openFirst;
	p_openFirst=NULL;   
   
    while(1)
		{//没有路径
         if(p_openHead->p_next==NULL)
		 {
			 cout<<endl<<"没有路径可走"<<endl;
			 return 0;
		 }
         //从open中取出第一个节点
         p_getOpenFirst=p_openHead->p_next;
         p_openHead->p_next=p_getOpenFirst->p_next;//删除open中第一个节点
         n_tempM=p_getOpenFirst->n_m;
         n_tempC=p_getOpenFirst->n_c;
         n_tempB=p_getOpenFirst->n_b;
		 n_tempStep=p_getOpenFirst->n_step;
		 n_tempSelfNumber=p_getOpenFirst->n_selfNumber;
         n_tempFatherNumber=p_getOpenFirst->n_fatherNumber;
         p_getOpenFirst=NULL;
         
		 //把从open取出的节点加入close的开头
         p_closeFirst=new Node;
         p_closeFirst->n_m=n_tempM;
         p_closeFirst->n_c=n_tempC;
         p_closeFirst->n_b=n_tempB;
		 p_closeFirst->n_step=n_tempStep;
         p_closeFirst->n_selfNumber=n_tempSelfNumber;
         p_closeFirst->n_fatherNumber=n_tempFatherNumber;
         
		 //插入close 头
		 p_closeFirst->p_next=p_closeHead->p_next;
         p_closeHead->p_next=p_closeFirst;
		 p_closeFirst=NULL;
			          
         //如果出现目标状态，结束循环
         if(n_tempM==0&&n_tempC==0&&n_tempB==0)
			 break;
		 for(i=0;i<3;i++)
			 {
			 for(j=0;j<3;j++)
				 {
                 if(!(i==0&&j==0||i==1&&j==2||i==2&&j==1||i==2&&j==2))
					 {
					 p_newNodeOfInsertOpen=new Node;
					 if(n_tempB==1)  //船在左岸的扩展方式
						 {
						  p_newNodeOfInsertOpen->n_m=n_tempM-i;
                          p_newNodeOfInsertOpen->n_c=n_tempC-j;
                          p_newNodeOfInsertOpen->n_b=0;
						 }
					 else           //船在右岸的扩展方式
						 {
						  p_newNodeOfInsertOpen->n_m=n_tempM+i;
                          p_newNodeOfInsertOpen->n_c=n_tempC+j;
                          p_newNodeOfInsertOpen->n_b=1;
						 }
				  //传教士生命安全
                  if((p_newNodeOfInsertOpen->n_m==3&&p_newNodeOfInsertOpen->n_c>=0)||
					 (p_newNodeOfInsertOpen->n_m==0&&p_newNodeOfInsertOpen->n_c>=0)||
					 (p_newNodeOfInsertOpen->n_m==2&&p_newNodeOfInsertOpen->n_c==2)||
					 (p_newNodeOfInsertOpen->n_m==1&&p_newNodeOfInsertOpen->n_c==1))
					  n_safe=1;
				  else
				  {
					  n_safe=0;					  
				  }
                 //open中出现过和预备插入结点p_newNodeOfInsertOpen相同状态的节点吗？
                 p_openCompare=p_openHead;
                 while(p_openCompare->p_next!=NULL)
					 {
					 p_openCompare=p_openCompare->p_next;
                     if(p_openCompare->n_m==p_newNodeOfInsertOpen->n_m&&
						p_openCompare->n_c==p_newNodeOfInsertOpen->n_c&&
						p_openCompare->n_b==p_newNodeOfInsertOpen->n_b)
						 {
						 n_openCompare=1;
						 continue;
						 }
					 else
						 {
						 n_openCompare=0;
						 }
					 }
				 p_openCompare=NULL;//内存安全
                 //close中出现过和预备插入结点p_newNodeOfInsertOpen相同状态的节点吗？
                 p_closeCompare=p_closeHead;
				 while(p_closeCompare->p_next!=NULL)
					 { 
					 p_closeCompare=p_closeCompare->p_next;
					 if(p_closeCompare->n_m==p_newNodeOfInsertOpen->n_m&&
						p_closeCompare->n_c==p_newNodeOfInsertOpen->n_c&&
						p_closeCompare->n_b==p_newNodeOfInsertOpen->n_b)
						 {
						 n_closeCompare=1;
						 continue;
						 }
					 else
						 {
						 n_closeCompare=0;
						 }
					  }
				 p_closeCompare=NULL;
                 //将刚产生的节点按照Fn()的从小到大的顺序插入open
				 if(n_safe==1&&n_openCompare==0&&n_closeCompare==0)
					 {
					  p_newNodeOfInsertOpen->n_selfNumber=++n_autoAddNumber;
					  p_newNodeOfInsertOpen->n_fatherNumber=n_tempSelfNumber;
					  p_newNodeOfInsertOpen->n_step=n_tempStep+1;

					  /////////////////////////////////////////////////////////////
					  p_beforeOpenNewInsert=p_openHead;
					  if(p_beforeOpenNewInsert->p_next==NULL)
					  {
						   p_newNodeOfInsertOpen->p_next=p_beforeOpenNewInsert->p_next;
						   p_beforeOpenNewInsert->p_next=p_newNodeOfInsertOpen;
        				   p_newNodeOfInsertOpen=NULL;  
					  }
					  else
					  {
						  while(p_beforeOpenNewInsert->p_next->Fn()<=p_newNodeOfInsertOpen->Fn())
							{
							  p_beforeOpenNewInsert=p_beforeOpenNewInsert->p_next;
							  if(p_beforeOpenNewInsert->p_next==NULL)
								  break;
							}
					      p_newNodeOfInsertOpen->p_next=p_beforeOpenNewInsert->p_next;
						  p_beforeOpenNewInsert->p_next=p_newNodeOfInsertOpen;
					      p_newNodeOfInsertOpen=NULL;  
					  }
					  //////////////////////////////////////////////////////////////
					 }
				 }
             }
		 }
	  }
	 //输出路径
	 p_closePrintFather=p_closeHead->p_next;
	 p_closePrintSon=p_closePrintFather;

	 cout<<"以下是渡河过程:"<<endl;
	 cout<<"   (M,C,B,F)"<<endl;
     cout<<"|--("<<p_closePrintFather->n_m<<","<<p_closePrintFather->n_c<<","
	 	 <<p_closePrintFather->n_b<<","<<p_closePrintFather->Fn()<<")"<<endl;
	 while(p_closePrintFather->p_next!=NULL)
		 {
		  p_closePrintFather=p_closePrintFather->p_next;
		  if(p_closePrintSon->n_fatherNumber==p_closePrintFather->n_selfNumber)
			  {
			   cout<<"<--("<<p_closePrintFather->n_m<<","<<p_closePrintFather->n_c<<","
				   <<p_closePrintFather->n_b<<","<<p_closePrintFather->Fn()<<")";
			   p_closePrintSon=p_closePrintFather;
			   cout<<endl;
			  }
		 }
	 p_closePrintFather=NULL;
	 p_closePrintSon=NULL;
     return(1);
}