栈----迷宫（Maze）-创新互联

大家都知道，至于迷宫的求解问题，可以用穷举法进行求解。那么什么是穷举法了，就是将每一种可能的情况都穷举完。而具体到迷宫的求解问题上，由于在求解过程中可能会遇到某一路径不可行的情况，此时我们就必须按原路返回，这时自然也就会想到栈的应用了，因为栈的一个很重要的特性就是”先进后出”，可以用来记录每次所探索的路径，方便在原路返回的过程中，得到上一步所走路径，再按此方法，退回到可以走得通的位置上，继续探索下去，直到到达终点或者最终无法到达，正常退出程序为止。

创新互联服务项目包括丰南网站建设、丰南网站制作、丰南网页制作以及丰南网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，丰南网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到丰南省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

   下面我们就一起来探索迷宫！！！

  首先是得到迷宫地图，这里我们用文件流来实现。

void GetMaze(int *a, size_t n)
{
	FILE* fout = fopen("MazeMap.txt", "r");  //打开迷宫地图
	assert(fout);
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 0; j < n;)
		{
			char ch = fgetc(fout);  //读取一个字符
			if (ch == '0' || ch == '1')
			{
				a[i*n + j] = ch - '0';
				j++;
			}
			else
			{
				continue;
			}
		}
	}
	fclose(fout);
}

给出迷宫地图：

0为通路，1为墙

 然后我们将迷宫打印出来

void PrintMaze(int* a, size_t n)
{
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 0; j < n; j++)
		{
			cout << a[i*n + j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

 接着定义位置结构体，用此结构体表示当前位置的横纵坐标

struct Pos
{
	int _row;
	int _col;
};

 然后再从给定的入口位置开始对此位置的上下左右四个相邻位置进行判断，若为1则行不通，若为0，则可以走，，并将此位置进行压栈。将走过的位置改为2，以备在回退的时候可以用

bool MazePath(int* a, size_t n, Pos& entry, stack& path)
{
	Pos cur = entry;
	path.push(cur);    //当前位置压栈
	while (!path.empty())
	{
		a[cur._row *n + cur._col] = 2;   //走过的位置标记为2
		Pos next = cur; //将当前位置进行标记
		//上
		next._row--;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		//右
		next = cur;
		next._col++;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		   //下
		next = cur;
		next._row++;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		  //左
		next = cur;
		next._col--;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		 //上下左右都走不通，回退
		cur = path.top();  
		path.pop();
		if (cur._row == n - 1)   // 出口
		{
			return true;
		}
	}
	return false;
}

判断当前位置的下一步是否走得通

bool CheckIsAccess(int* a, size_t n, Pos next)
{
	assert(a);
	if ((next._col >= 0) && (next._col < n) && (next._row >= 0) && (next._row < n) &&
		(a[next._row *n + next._col] == 0))
	{
		return true;
	}
	else
		return false;
}

这样一个简单的迷宫就完成了，是不是看起来挺容易的呢？如果有不懂得地方，欢迎留言。有高见也欢迎留言~

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

分享标题：栈----迷宫（Maze）-创新互联
文章地址：http://cdxtjz.cn/article/dcigpe.html