走迷宫问题（待续）

前言：

我的地图文件（MazeMap.txt）如下：

size:(a,a) 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1

下面的pos类用来保存某个位置的坐标

GetMaze函数用来判断地图格式的合法性，若合法则读取地图内容，并将内容存入参数arr所指向的内存中。

struct pos {	pos(int row = 0, int col = 0)	:_row(row)	,_col(col)	{}	int _row;	int _col; }; void GetMaze(int *&arr, int &sz, int &row, int &col) {	FILE *fout = fopen("MazeMap.txt", "r");	assert(fout);	char *title = new char[40];	title = fgets(title, 7, fout);	if (strcmp(title, "size:("))	{	cout << "地图文件错误！" << endl;	throw 1;	}	row = fgetc(fout) - 87;	title = fgets(title, 2, fout);	if (strcmp(title, ","))	{	cout << "地图文件错误！" << endl;	throw 1;	}	col = fgetc(fout) - 87;	arr = new int[row * col];	sz = row * col;	title = fgets(title, 2, fout);  	for (int i = 0; i < sz; i)	{	char ch = fgetc(fout);	if (ch != ' ' && ch != '\n' && ch != '\0')	{	*(arr + i) = ch - '0';	i++;	}	} }

一、找到出口

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()); }

三、优化后的算法

四、用递归实现

//待续