走迷宮問題（待續）

前言：

我的地圖文件（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());
}

三、優化后的算法

四、用遞歸實現

//待續