迷宫问题.cpp

用stl实现的迷宫问题算法!(源创) 在这里你将看到stl的强大和方便!

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

class state
{
public:
	int m_pos;
	int m_flag;
	int m_fatherPos;

	bool operator ==(const state& s)
	{
		if(m_pos==s.m_pos)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	state& operator =(const state& s)
	{
		if((*this)==s)
		{
		return *this ;
		}
		else
		{
			m_pos=s.m_pos;
			m_flag=s.m_flag;
			m_fatherPos=s.m_fatherPos;
		}
		return *this;
	}

};

void main()
{
	//input
	int n;
	cout<<"please input the length of the maze!"<<endl<<endl;
	cin>>n;
    map<int,int> maze;
	vector<state> open;
	open.reserve(n*n);
	vector<state>::iterator iter;
	vector<state>::iterator it;
	
    cout<<"please input the maze!"<<endl<<endl;
	int flag=0;
	int pos=0;

	for(int i=0;i<n*n;i++)
	{
		cin>>flag;
	    maze[pos]=flag;
        pos++;
	}

	cout<<"please input the entrance and exit!"<<endl<<endl;
	state entrance;
	state exit;
	cin>>pos;
	entrance.m_pos=pos;
	entrance.m_fatherPos=-1;
	cin>>pos;
	exit.m_pos=pos;
	open.push_back(entrance);
	it=open.begin();

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

		if(father==exit)
		{
			break;
		}	
        
		if(father.m_pos/n>0 && maze[father.m_pos-n]==1)//往上走
		{   
			state sun;
			sun=father;
			sun.m_pos=father.m_pos-n;
			sun.m_fatherPos=father.m_pos;
            
			//如果sun为全新的节点，将sun插入open表.    
			if((iter=find(open.begin(),open.end(),sun))==open.end())
			{
				open.push_back(sun);
			}
		}

		 if(father.m_pos%n>0 && maze[father.m_pos-1]==1)//往左走
		{   
			state sun;
			sun=father;
			sun.m_pos=father.m_pos-1;
			sun.m_fatherPos=father.m_pos;
            
			//如果sun为全新的节点，将sun插入open表.    
			if((iter=find(open.begin(),open.end(),sun))==open.end())
			{
				open.push_back(sun);
			}
		 }


        if(father.m_pos/n<n-1 && maze[father.m_pos+n]==1)//往下走
		{   
			state sun;
			sun=father;
			sun.m_pos=father.m_pos+n;
			sun.m_fatherPos=father.m_pos;
            
			//如果sun为全新的节点，将sun插入open表.    
			if((iter=find(open.begin(),open.end(),sun))==open.end())
			{
				open.push_back(sun);
			}
		}

          if(father.m_pos%n<n-1 && maze[father.m_pos+1]==1)//往右走
		  {   
			state sun;
			sun=father;
			sun.m_pos=father.m_pos+1;
			sun.m_fatherPos=father.m_pos;
            
			//如果sun为全新的节点，将sun插入open表.    
			if((iter=find(open.begin(),open.end(),sun))==open.end())
			{
				open.push_back(sun);
			}
		  }

		}//while(1)

	    	//output
			if(it-1!=open.end())
			{
				state sun;
				sun=(*(it-1));
				int x=sun.m_fatherPos;
				cout<<"the path is:"<<endl;
				cout<<"("<<sun.m_pos/n<<sun.m_pos%n<<")"<<endl;

				while(x!=-1)
				{
					cout<<"("<<x/n<<x%n<<")"<<endl;
					iter=open.begin();
					while(iter!=open.end())
					{
						if((*iter).m_pos==x)
						{
							break;
						}
						else
						{
							iter++;
						}
					}
					
					x=(*iter).m_fatherPos;
				}
			}
		}