迷宫问题并求最短路径-创新互联

#include 
#include 
#include 
#include 

struct Pos
{
	int _row;
	int _col;
};

bool MinPath(vector>& maze, int row, int col, Pos enrty, stack& minPath)
{
	assert(!maze.empty());
	stack path;
	bool firstOrNo = true;
	vector> tmp = maze;
	while (maze[enrty._row][enrty._col] != 3)
	{
		tmp = maze;
		path.push(enrty);
		while (!path.empty())
		{
			Pos cur = path.top();
			tmp[cur._row][cur._col] = 2;
			if (path.top()._row == row - 1)
			{
				maze[path.top()._row][path.top()._col] = 4;
				if (firstOrNo || path.size() < minPath.size())
				{
					minPath = path;
					firstOrNo = false;
				}
				while (!path.empty())
				{
					path.pop();
				}
				break;
			}
			//上
			Pos next = cur;
			next._row--;
			if (next._row >= 0 && next._row < row
				&&next._col >= 0 && next._col < col
				&&tmp[next._row][next._col] == 0)
			{
				path.push(next);
				continue;
			}
			//下
			next = cur;
			next._row++;
			if (next._row >= 0 && next._row < row
				&&next._col >= 0 && next._col < col
				&&tmp[next._row][next._col] == 0)
			{
				path.push(next);
				continue;
			}
			//左
			next = cur;
			next._col--;
			if (next._row >= 0 && next._row < row
				&&next._col >= 0 && next._col < col
				&&tmp[next._row][next._col] == 0)
			{
				path.push(next);
				continue;
			}
			//右
			next = cur;
			next._col++;
			if (next._row >= 0 && next._row < row
				&&next._col >= 0 && next._col < col
				&&tmp[next._row][next._col] == 0)
			{
				path.push(next);
				continue;
			}
			maze[path.top()._row][path.top()._col] = 3;
			path.pop();
		}//while !empty(path)

	} //while 大

	//在地图中标出最短路径
	stack p = minPath;
	while (!p.empty())
	{
		maze[p.top()._row][p.top()._col] = 2;
		p.pop();
	}
	
	return !minPath.empty();
}

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

创新互联公司-专业网站定制、快速模板网站建设、高性价比延安网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式延安网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖延安地区。费用合理售后完善，十多年实体公司更值得信赖。
分享文章：迷宫问题并求最短路径-创新互联
文章起源：http://bzwzjz.com/article/coiooi.html