广度搜索与八数码游戏.cpp

八数码游戏的不同实现方法! 1.八数码游戏与A*算法的结合! 本程序主要是给出一个A*算法的示例!效率并不高 2.广度算法 这个效率还可以的!

#pragma warning(disable:4786)
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<cmath>
#include<map>
using namespace std;

const N=6;

map<int,int> sonFather;//根据sun的m_name找父亲的m_name;
map<int,int>::iterator ite;

class A
{
public:


	A(char a[N][N])
	{
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
			m_a[i][j]=a[i][j];
			}
		}
        m_name=0;
	}

	bool operator ==(const A& a)
	{
		for(int i=0;i<N;i++)
		{
		for(int j=0;j<N;j++)
			{
				if(a.m_a[i][j]!=m_a[i][j])
				{
					return false;
				}
			}
		}
		
		return true;
	}

 
	void print()
	{
		for(int i=0;i<N;i++)
		{   
			for(int j=0;j<N;j++)
			{
				cout<<m_a[i][j]<<"	";
			}

			cout<<endl<<endl<<endl;
		}
	}

public:
 	char m_a[N][N];
	int m_name;

};	


void main()
{
	char a[N][N]={'1', '2', '3', ' '};
        char b[N][N]={'3', '1', ' ', '2'};
//	char a[N][N]={'1','2','3','8',' ','4','7','6','5'};
//	char b[N][N]={'1','5','8','2','6',' ','4','7','3'};
	A soure(a);
	soure.m_name=0;
	A aim(b);
    vector<A> open;
	open.reserve(200000);
    vector<A>::iterator iter;
	vector<A>::iterator it;
	open.push_back(soure);
    sonFather.insert(make_pair(0,0));
	it=open.begin();
	int name=1; 

	while(1)
	{
		cout<<name<<endl;
        if(it==open.end())
		{
			cout<<"There is no trace from soure to aim!"<<endl;
				break;
		}
       
        A father((*it).m_a);//即将扩展的节点
		father.m_name=(*it).m_name;
        it++;

		if(father==aim)
		{
			break;
		}	
		
        //找出空格子所在的位置。便于扩展子节点。
        int m,n;
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				if(father.m_a[i][j]==' ')
				{
					m=i;
					n=j;
					break;
				}
			}
		}
        
		if(m<N-1)//往上移
		{   
			A sun(father.m_a);
		    swap(sun.m_a[m+1][n],sun.m_a[m][n]);
            
			//如果sun为全新的节点，将sun插入open表.    
			if((iter=find(open.begin(),open.end(),sun))==open.end())
			{
			    sun.m_name=name; 
				sonFather.insert(make_pair(sun.m_name,father.m_name));
				name++;
				open.push_back(sun);
			}
		}

        if(m>0)//往下移
		{   
			A sun(father.m_a);
		    swap(sun.m_a[m-1][n],sun.m_a[m][n]);
           
			if((iter=find(open.begin(),open.end(),sun))==open.end())
			{
			    sun.m_name=name; 
			    sonFather.insert(make_pair(sun.m_name,father.m_name));
				name++;
				open.push_back(sun);
			}
		}

         if(n<N-1)//往左移
		{   
			A sun(father.m_a);
		    swap(sun.m_a[m][n+1],sun.m_a[m][n]);

			if((iter=find(open.begin(),open.end(),sun))==open.end())
			{
			    sun.m_name=name; 
				sonFather.insert(make_pair(sun.m_name,father.m_name));
				name++;
				open.push_back(sun);
			}
		 }

          if(n>0)//往右移
		  {   
			A sun(father.m_a);
		    swap(sun.m_a[m][n-1],sun.m_a[m][n]);

			if((iter=find(open.begin(),open.end(),sun))==open.end())
			{
			    sun.m_name=name; 
				sonFather.insert(make_pair(sun.m_name,father.m_name));
				name++;
				open.push_back(sun);
			}
		  }

		}//while(1)

	    	//output
			cout<<name<<endl<<endl;//节点的个数
			if(it-1!=open.end())//找到路径
			{
				A sun((*(it-1)).m_a);
				sun.m_name=(*(it-1)).m_name;
				int x=sun.m_name;
				sun.print();

				while(x!=0)
				{
					iter=open.begin();
					while(iter!=open.end())
					{
						if((*iter).m_name==sonFather[x])
						{
							break;
						}
						else
						{
							iter++;
						}
					}

					A sun((*iter).m_a);
				    sun.m_name=(*iter).m_name;
					x=sun.m_name;
					cout<<endl<<endl<<endl<<endl;
			    	sun.print();

				}
			}

			/*else//打印所有的接点。
			{
				iter=open.begin();
				while(iter!=open.end())
				{
					(*iter).print();
					iter++;
				}
			}*/
		}