利用数据结构栈求解迷宫有关问题

利用数据结构栈求解迷宫问题

本段程序主要利用数据结构栈的先进后出特点，实现回溯求解迷宫路径问题。

#include<iostream>
#include<stack>
using namespace std;
//坐标类
struct Point
{
	int x;
	int y;
};
//地图类
template<int A>
struct Map
{
	int (*p)[A];
	int row;//行数
	int col;//列数
};
//start起始点， end终止点
template<int A>
bool FindPath(Map<A> & map,Point & start,Point & end)
{
	//先给图的外围加上障碍
	for(int i = 0;i<=map.col;i++)
	{
		map.p[0][i] = map.p[map.row][i] = 1;
	}
	for(int i = 0;i<=map.row;i++)
	{
		map.p[i][0] = map.p[i][map.col] = 1;
	}

	//用于保存路径的栈
	stack<Point> stackpath;
	//用于方向选择的偏移量数组   按照顺时针的方向
	Point offset[4];
	offset[0].x = 0; offset[0].y = 1;//向右
	offset[1].x = 1; offset[1].y = 0;//向下
	offset[2].x = 0; offset[2].y = -1;//向左
	offset[3].x = -1; offset[3].y = 0;//向上

	//将起点初始化为障碍点
	map.p[start.x][start.y] = 1;
	//起点入栈
	stackpath.push(start);
	//用于下一步方向选择的变量
	int option = 0;
	//下一步的最大选择变量
	int MaxOption = 3;
	//
	while((start.x != end.x)||(start.y != end.y))
	{
	 //选择下一步
		  while(option<=MaxOption)
		 {
			int x =  start.x + offset[option].x;
			int y =  start.y + offset[option].y;
			 if(map.p[x][y]!=1)
			 {
				 start.x = x;
				 start.y = y;
				 break;
			 }
			 option++;
		 }
		  //如找到了下一点
		  if(option<=MaxOption)
		  {
		   //入栈
		   stackpath.push(start);
		   //设置障碍
		   map.p[start.x][start.y] = 1;
		   option = 0;
		  }
		  else//没找到了下一点
		  {
			  //向后退一步，出栈
			  stackpath.pop();
			
			  //消除入栈时设置的障碍
			  map.p[start.x][start.y] = 0;
			  if(stackpath.empty())
			  {
				  return false;
			  }
			  //设置回溯后的option
			  if(start.x == stackpath.top().x)
			  {
				  if((start.y - stackpath.top().y)==1)//向右
				  {
					   option = 0;
				  }
				  if((start.y - stackpath.top().y)==-1)//向左
				  {
					   option = 2;
				  }
			  }
			  if(start.y == stackpath.top().y)
			  {
			  
				  if((start.x - stackpath.top().x)==1)//向下
				  {
				      option = 1;
				  }
				   if((start.x - stackpath.top().x)==-1)//向上
				  {
				      option = 3;
				  }
			  }
			  option++;
			  start.x = stackpath.top().x;
			  start.y = stackpath.top().y;
		  }
	}
	//找到路径，并输出stackpath
	while(!stackpath.empty())
	{
		cout<<"<"<<stackpath.top().x<<","<<stackpath.top().y<<">"<<endl;
		stackpath.pop();
	}
	return true;
}

int main()
{
	//建立迷宫
	Map<10> map;
	map.col = map.row = 9;
	int p[10][10];
	for(int i =0;i<10;i++)//初始化迷宫
	{
	 for(int j=0;j<10;j++)
	 {
		 p[i][j] = 0;
	 }
	}
	//为迷宫设置障碍
	p[1][3] = 1;p[1][7] = 1;p[2][3] = 1;p[2][7] = 1;
	p[3][5] = 1;p[3][6] = 1;p[4][2] = 1;p[4][3] = 1;
	p[4][4] = 1;p[5][4] = 1;p[6][2] = 1;p[6][6] = 1;
	p[7][2] = 1;p[7][3] = 1;p[7][4] = 1;p[7][6] = 1;
	p[8][1] = 1;
	map.p = p;
	Point start,end;
	start.x = start.y = 1;
	end.x =8,end.y = 8;
	if(!FindPath<10>(map,start,end))
	{
	  cout<<"该迷宫无解！"<<endl;
	}
}