迷宮問(wèn)題并求最短路徑

#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 大

	//在地圖中標(biāo)出最短路徑
	stack<Pos> p = minPath;
	while (!p.empty())
	{
		maze[p.top()._row][p.top()._col] = 2;
		p.pop();
	}
	
	return !minPath.empty();
}

本文題目：迷宮問(wèn)題并求最短路徑
文章轉(zhuǎn)載：http://bm7419.com/article12/gijdgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、標(biāo)簽優(yōu)化、做網(wǎng)站、品牌網(wǎng)站制作、網(wǎng)站維護(hù)、營(yíng)銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)