maze_2.cpp

数据结构迷宫

#include <iostream.h>
#include <iomanip.h>



//迷宫阵
int Maze[11][10]={  {1,1,1,1,1,1,1,1,1,1},
					{1,0,0,1,0,0,0,1,0,1},
					{1,0,0,1,0,0,0,1,0,1},
					{1,0,0,0,0,1,1,0,1,1},
					{1,0,1,1,1,0,0,1,0,1},
					{1,0,0,0,1,0,0,0,0,1},
					{1,0,1,0,0,0,1,0,1,1},
					{1,0,1,1,1,1,0,0,1,1},
					{1,1,1,0,0,0,1,0,1,1},
					{1,1,1,0,0,0,0,0,0,1},
					{1,1,1,1,1,1,1,1,1,1} };
//位置点数据结构
struct point
{
	int row;
	int col;
	point *pre;
};
//迷宫通道堆栈
class passage
{
public:
	passage();
	bool Push( point * );
	bool Pop();
	point *base;
	point *top;
};
passage::passage()
{
	base = new point;
	top  = base;
}
bool passage::Push(point * e)
{
	e->pre = top->pre ;
	top->pre = e;
	return true;
}
bool passage::Pop()
{
	top = top->pre;
	return true;
}
//输出迷宫
void intputMaze()
{
	cout<<"********测试迷宫阵********"<<endl; 
	cout<<"    0 通道，1 障碍物 "<<endl;
	cout<<" (起始点(1,1),终点(8,9))"<<endl;
	cout<<"--------------------------"<<endl;
	for(int i=1; i<10; i++)
	{
		for(int j=1; j<9; j++)
		{
			cout<<setw(3)<<Maze[i][j];
		}
		cout<<endl;
	}
	cout<<"--------------------------"<<endl;
}
//走迷宫
bool FindPath()
{
	point offset[4];
	offset[0].row = 1;
	offset[0].col = 0;
	offset[1].row = 0;
	offset[1].col = 1;
	offset[2].row = 0;
	offset[2].col =-1;
	offset[3].row =-1;
	offset[3].col = 0;
	
	passage path;
	point here;
	here.row = 1;
	here.col = 1;
	path.Push( & here);
	Maze[here.row][here.col] = 2;
	
	while(!(here.row == 9 && here.col == 8))
	{
		int r,c;
		int direction=0;
		int count = 0;
		while(direction < 4)
		{
			r = here.row + offset[direction].row ;
			c = here.col + offset[direction].col ;
			if( Maze[r][c] == 0)
			{
				point * d_here;
				d_here = new point;
				d_here->row = here.row;
				d_here->col = here.col;
				Maze[here.row][here.col] = 2;
				here.row = r;
				here.col = c;
				path.Push(d_here);
				break;
			}
			else
			{
				direction++;
				count++;
			}
		}
		if(count == 4 )
		{
			Maze[here.row][here.col] = 1;
			here.row = path.top->pre->row ;
			here.col = path.top->pre->col ;
			path.Pop();
		}
	}
	cout<<"通路：2代表走过的地方"<<endl;
	for(int i=1; i<10; i++)
	{
		for(int j=1; j<9; j++)
		{
			cout<<setw(3)<<Maze[i][j];
		}
		cout<<endl;
	}
	return true;
}

//测试
void main()
{
	intputMaze();
	if( FindPath() )
		cout<<"恭喜走出迷宫"<<endl;
	else
		cout<<"该迷宫无出口"<<endl;
	cout<<"测试完毕，敬请指教"<<endl;
}