maze.cpp

用栈实现的迷宫算法

//        程序名：maze.cpp
//      程序功能：用栈实现找迷宫路径
//          作者：骆宏峰
//          日期：2006.11.6
//          版本：1.0     
//
//
//////////////////////////////////////////////////////////////////////////////
#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<fstream.h>
//////////////////////////////////////////////////////////////////////////////
typedef struct Pos            
{
	int x,y,dir;
}DataType;

struct ListNode
{
	DataType data;
	struct ListNode *next;
};

struct
{
	int x,y;
}move[4]={{0,1},{1,0},{0,-1},{-1,0}};


class Stack
{
public:
	ListNode *top;
	int Top;
	
public:
	Stack()                          //构造函数
	{
		top=new ListNode;
        top->next=NULL;
	}
	~Stack()                         //析构函数  
	{
		ListNode *p;
		p=new ListNode;
		while(top!=NULL)
		{
			p=top;
			top=top->next;
			delete p;
		}
	}
	
	void Path(int **p,int m,int n);        //求路径函数
	void Push(DataType x);                 //入栈函数 
	void Pop();                            //出栈函数
	int IsEmpty();                         //判断是空函数
	void PrintPath();                      //打印函数
};
//////////////////////////////////////////////////////////////////////////////
//入栈函数
//参数：要压入粘中的DataType
//返回值：无
//功能：压栈
void Stack::Push(DataType x)
{
	ListNode *p;
	p=new ListNode;
	p->data=x;
	p->next=top;
	top=p;                        //记录栈中元素的个数
}
//////////////////////////////////////////////////////////////////////////////
//出栈函数
//参数：无
//返回值：无
//功能：将死路的坐标出栈
void Stack::Pop()
{
	ListNode *p;
	if(top==NULL) cout<<"0";
	else
	{
		p=top;
		top=top->next;
		delete p;
	}
}
//////////////////////////////////////////////////////////////////////////////
//名判断是空函数
//参数：无
//返回值：空返回“1”，非空返回NULL
//功能：判空
int Stack::IsEmpty()
{
	if(top==NULL)
		return 1;
	else
		return NULL;
}
//////////////////////////////////////////////////////////////////////////////
//求路径函数
//参数：储存迷宫的m*n数组，m和n
//返回值：无
//功能：找出一条路径，无路径则输出“没有路径”
void Stack::Path(int **a,int m,int n)
{
    Top=1;
	DataType Temp;
	int x,y;
	int i=0;
	Temp.x=1;
	Temp.y=1;
	Push(Temp);
	a[1][1]=-1;
	while(!IsEmpty())
	{
		x=Temp.x+move[i].x;
		y=Temp.y+move[i].y;
		if(a[x][y]==0)
		{
			Temp.x=x;
			Temp.y=y;
			Temp.dir=i+1;                  //此方向为上一个坐标的方向
			a[x][y]=-1;
			Push(Temp);
			Top++;
			if((x==m)&&(y==n))             //找到最后的坐标，打印路径，退出循环
			{
				PrintPath();
				break;
			}
			i=0;
		}
		else if(i==3)
		{
		    Pop();
			Top--;
			if(top->next==NULL)
			{
				cout<<"没有路径"<<endl;
				break;
			}
			else
				Temp=top->data;
			i=0;
		}
		else if(i<3)
			i++;
    }
}
//////////////////////////////////////////////////////////////////////////////
//打印函数
//参数：无
//返回值：无
//功能：把栈中的元素整理打印
void Stack::PrintPath()
{
	int j=Top;
	DataType *t=new DataType[j];
	for(int i=0;i<j;i++)
	{
		t[i]=top->data;
		top=top->next;
	}
	for(int h=j-1;h>0;h--)                //把方向和坐标对应
	{
		t[h].dir=t[h-1].dir;
	}
    t[0].dir=0;
	for(int k=j-1;k>=0;k--)
	{
		cout<<"("<<t[k].x<<","<<t[k].y<<","<<t[k].dir<<")";
	}
	cout<<endl;

}
//////////////////////////////////////////////////////////////////////////////
//main函数
//参数：无
//返回值：无
void main()
{
	cout<<"*******************************迷宫**************************************"<<endl;
	int n,m;
	cout<<"输入一个m*n迷宫"<<endl;
	cout<<"输入m："<<endl;
	cin>>m;
	cout<<"输入n："<<endl;
	cin>>n;
	cout<<"输入迷宫数据："<<endl;
    ofstream fop;              
	fop.open("test.txt");         //以写入文件的形式打开文件
	int **a;
	a=new int*[m+2];
	for(int i=0;i<m+2;i++)        //新建一个m*n维的数组
		a[i]=new int[n+2];
	for(i=0;i<m+2;i++)            //输入数组的元素          
	{
		for(int j=0;j<n+2;j++)  
		{
			if(i==0||j==0||i==m+1||j==n+1)    //外围全部为1      
			{
 				a[i][j]=1;
				fop<<a[i][j];               
			}
			else
			{
				cin>>a[i][j];
			    fop<<a[i][j];
			}
		}
		
	}
	flush(cout);
	fop.close();
	cout<<"整理后的迷宫为："<<endl;
	int **b;
	b=new int*[m+2];
	for(i=0;i<m+2;i++)
		b[i]=new int[n+2];
	char ch;
	ifstream fip("test.txt");          //以读取的形式打开文件
	int k=0;
	for(i=0;i<m+2;i++)
	{
		for(int j=0;j<n+2;j++)
		{
			fip.get(ch);
			b[i][j]=ch-'0';             //读取出来的char类型转换后存入另一个数组
			cout<<ch<<"   ";            //打印整理后的数组
			k++;
			if(k%(n+2)==0)
				cout<<endl;
		}
	}
	fip.close();
	cout<<"路径为："<<endl;

	Stack s;
	s.Path(b,m,n);                       //对象调用求路径函数
}