走迷宫问题（待续）

前置代码：

struct pos
{
	pos(int row = 0, int col = 0)
		:_row(row)
		,_col(col)
	{}
	int _row;
	int _col;
};

void GetMaze(int *arr,  int n)
{
	FILE *fout = fopen("MazeMap.txt", "r");
	assert(fout);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n;)
		{
			char ch = fgetc(fout);
			if (ch != ‘ ‘ && ch != ‘\n‘)
			{
				*(arr + i * n + j) = ch - ‘0‘;
				j++;
			}
		}
	}
}

一、找到出口

bool MazePath(int *arr, int n, const pos &entry, stack<pos> &path)   //假设下边沿为迷宫的出口
{
	pos cur = entry;
	path.push(cur);
	while (!path.empty())
	{
		*(arr + n * (cur._row)+cur._col) = 2;
		if (cur._row == n - 1)
		{
			return true;
		}
		//向下
		if 
		((cur._row + 1 < 10) && (*(arr + n * (cur._row + 1) + cur._col) == 0)) 
		{
			*(arr + n * (cur._row + 1) + cur._col) = 2;
			++cur._row;
			path.push(cur);
			continue;
		}
		//向上
		if 
		((cur._row - 1 >= 0) && (*(arr + n * (cur._row - 1) + cur._col) == 0))  
		{
			*(arr + n * (cur._row - 1) + cur._col) = 2;
			--cur._row;
			path.push(cur);
			continue;
		}
		//向左
		if 
		((cur._col - 1 >= 0) && (*(arr + n * cur._row + cur._col - 1) == 0))     
		{
			*(arr + n * cur._row + cur._col - 1) = 2;
			--cur._col;
			path.push(cur);
			continue;
		}
		//向右
		if ((cur._col + 1 < 10) && (*(arr + n * cur._row + cur._col + 1) == 0))      
		{
			*(arr + n * cur._row + cur._col + 1) = 2;
			++cur._col;
			path.push(cur);
			continue;
		}

		//走不通
		cur._col = path.top()._col;
		cur._row = path.top()._row;
		path.pop();
	}
}

二、找到所有出口并得出最短路线（最优解）

template <typename T>
void ClearPath(stack<T> &stack)
{
	while (!stack.empty())
	{
		stack.pop();
	}
}

static void SaveBestPath(stack<pos> &path, vector< stack<pos> > path_vec)
{
	stack<pos> best_path;
	int sz = (path_vec.back()).size();
	best_path = path_vec.back();
	while (!path_vec.empty())
	{
		if (sz > (path_vec.front()).size())
		{
			best_path = path_vec.front(); 
		}
		path_vec.pop_back();
	}
	path = best_path;
}

static struct Exit
{
	Exit(int row, int col)
		:_row(row)
		,_col(col)
	{}
	int _row;
	int _col;
};

 //堵住已知的出口    (为了不销毁数据，不使用引用)
static void BlockKnownExit(int *arr, vector< Exit> exit_vec, int n)		
{
	Exit ext1 = exit_vec.back();
	while (!exit_vec.empty())
	{
		ext1 = exit_vec.back();
		*(arr + n * ext1._row + ext1._col) = 3;
		exit_vec.pop_back();
	}
}

//假设下边沿为迷宫的出口
bool MazePathMin(int *arr, int n, const pos &entry, stack<pos> &path)  
{
	vector< stack<pos> > path_vec;   //用于存放所有的路径
	vector< Exit > exit_vec;         //用于存储所有出口
	pos cur = entry;
	path.push(cur);

	while (!path.empty() )
	{
		*(arr + n * (cur._row) + cur._col) = 2;
		if (cur._row == n - 1)
		{
			//找到一个出口
			*(arr + n * (cur._row) + cur._col) = 3;
			Exit ext_tmp(cur._row, cur._col);
			path_vec.push_back(path);
			exit_vec.push_back(ext_tmp);

			//清空路径，寻找除该出口外的其他出口
			ClearPath(path);
			GetMaze(arr, n);
			BlockKnownExit(arr, exit_vec, n);
			cur = entry;
			path.push(cur);
		}
                 //向下
		if ((cur._row + 1 < 10) && (*(arr + n * (cur._row + 1) + cur._col) == 0))
		{
			*(arr + n * (cur._row + 1) + cur._col) = 2;
			++cur._row;
			path.push(cur);
			continue;
		}
		//向上
		if ((cur._row - 1 >= 0) && (*(arr + n * (cur._row - 1) + cur._col) == 0))  
		{
			*(arr + n * (cur._row - 1) + cur._col) = 2;
			--cur._row;
			path.push(cur);
			continue;
		}
		//向左
		if ((cur._col - 1 >= 0) && (*(arr + n * cur._row + cur._col - 1) == 0))     
		{
			*(arr + n * cur._row + cur._col - 1) = 2;
			--cur._col;
			path.push(cur);
			continue;
		}
		//向右
		if ((cur._col + 1 < 10) && (*(arr + n * cur._row + cur._col + 1) == 0))      
		{
			*(arr + n * cur._row + cur._col + 1) = 2;
			++cur._col;
			path.push(cur);
			continue;
		}

		//走不通的时候：
		cur._col = path.top()._col;
		cur._row = path.top()._row;
		path.pop();
	}

	//path为空
	SaveBestPath(path, path_vec);   //把最佳的路径保存进path中（仍然倒序）
	return (!path.empty());
}

三、用递归实现

本文出自 “思考时间” 博客，请务必保留此出处http://zhweizhi.blog.51cto.com/10800691/1762467

走迷宫问题（待续）

原文：http://zhweizhi.blog.51cto.com/10800691/1762467