111.cpp

可以在一个给定的迷宫中找出出口

#include<iostream>
#include<fstream>
using namespace std;
#define OK 0
#define ERROR 1
typedef int Status;
const int maxsize=15;
int a[maxsize][maxsize];
class node
{
public :
	int x;
	int y;
	int data;
	node *next;
};//运用结点
class stack
{
public:
	stack();
	~stack();
	void push(int col,int row, int number);
	void pop();
    Status gettop(int &col,int &row,int &data1);
	int size;
private:
	node * head;
	node * top;
};//新建的STACK类
stack::stack()
{
    head=top=new(node);
	size=0;
}//同构函数
stack::~stack()
{
	node *p;
	p=head;
	while(p->next)
	{
		head=head->next;
		delete(p);
		p=head;
	}
	delete(head);
}//析构函数
void stack::push(int col,int row,int  number)
{
	node *p=new (node);
	p->data=number;
	p->x=col;
	p->y=row;
	p->next=top;
	top=p;
	a[row][col]=2;
	size++;
}//进栈
void stack::pop()
{
	a[top->y][top->x]=3;
	top=top->next;
	size--;
}//出栈
Status stack::gettop(int &col,int &row,int &data1)
{
	if(size==0)
	{cout<<"there is no end;"<<endl;	exit(1);}

	else
	{
	   row=top->y;
	   col=top->x;
	   data1=top->data;
	   return OK;
	}
}//获取栈头
void findend(stack & stack1,int ox,int oy)
{
	int col,row, data1;
	stack1.gettop(col,row,data1);
	if(col==ox&&row==oy)
	{
		int length=stack1.size;
	    while(length>0)
		{ 
           int col,row,data1;
		   stack1.gettop(col,row,data1);
		   stack1.pop();
		   cout<<"("<<col<<","<<row<<")"<<" ";
		   length--;
		}
		cout<<endl;
	    for(int i=0;i<10;i++)
	      {for(int j=0;j<10;j++)
			  cout<<a[i][j]<<" ";
	          cout<<endl;}
		exit(0);
	}
	else
	{
		int col,row, data1;
	    stack1.gettop(col,row,data1);
		int k;
		if(a[row][col+1]==0 &&col+1<10)
		{k=a[row][col+1];stack1.push(col+1,row,k);findend(stack1, ox, oy);}
		if(a[row+1][col]==0 &&row+1<10)
		{k=a[row+1][col];stack1.push(col,row+1,k);findend(stack1, ox, oy);}
		if(a[row][col-1]==0 &&col-1>=0)
		{k=a[row][col-1];stack1.push(col-1,row,k);findend(stack1, ox, oy);}
		if(a[row-1][col]==0 &&row-1>=0)
		{k=a[row-1][col];stack1.push(col,row-1,k);findend(stack1, ox, oy);}
        stack1.pop();findend(stack1,ox,oy);
	}
}//寻找终点的函数
int  main()
{
	ifstream infile;
	infile.open("migong.txt");
	if(!infile)
	{cout<<"can't open the file!"<<endl;return 1;}
	for(int i=0;i<10;i++)
	   for(int j=0;j<10;j++)//从文件读取数据（迷宫）
	       infile>>a[i][j];
	   
	for( i=0;i<10;i++)
	   {for(int j=0;j<10;j++)
		 cout<<a[i][j]<<" ";
	       cout<<endl;}

	int ix,iy,ox,oy;
	cout<<"please enter the point of entrance (col first and row last):"<<endl;
    cin>>ix>>iy;//让用户输入起点

	cout<<"please enter the point of end(col first and row last):"<<endl;
	cin>>ox>>oy;//再由用户定义终点

	if(a[iy][ix]!=0)
	{cout<<"the "<<ix<<" "<<iy<<" is not the entrance!"<<endl;return 1;}//判断起点是否真确

	stack stack1;
	stack1.push(ix,iy,a[iy][ix]);
	findend(stack1,ox,oy);

	return 0;
}