迷宫问题并求最短路径

#include <iostream>
#include <cassert>
#include <stack>
#include <vector>

struct Pos
{
	int _row;
	int _col;
};

bool MinPath(vector<vector<int>>& maze, int row, int col, Pos enrty, stack<Pos>& minPath)
{
	assert(!maze.empty());
	stack<Pos> path;
	bool firstOrNo = true;
	vector<vector<int>> 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<Pos> p = minPath;
	while (!p.empty())
	{
		maze[p.top()._row][p.top()._col] = 2;
		p.pop();
	}
	
	return !minPath.empty();
}

本文题目：迷宫问题并求最短路径
文章转载：https://www.cdcxhl.com/article12/gijdgc.html

成都网站建设公司_创新互联，为您提供外贸建站、标签优化、做网站、品牌网站制作、网站维护、营销型网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联