走迷宮問題（待續(xù)）-創(chuàng)新互聯(lián)

前言：

10年積累的成都網(wǎng)站建設、做網(wǎng)站經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站設計后付款的網(wǎng)站建設流程，更有化隆免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

我的地圖文件（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函數(shù)用來判斷地圖格式的合法性，若合法則讀取地圖內(nèi)容，并將內(nèi)容存入?yún)?shù)arr所指向的內(nèi)存中。

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

二、找到所有出口并得出最短路線（最優(yōu)解）

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

 //堵住已知的出口    (為了不銷毀數(shù)據(jù)，不使用引用)
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());
}

三、優(yōu)化后的算法

四、用遞歸實現(xiàn)

//待續(xù)

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證，機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務器買多久送多久。

網(wǎng)站題目：走迷宮問題（待續(xù)）-創(chuàng)新互聯(lián)
標題路徑：http://bm7419.com/article32/dgoppc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供域名注冊、網(wǎng)站改版、Google、網(wǎng)站制作、軟件開發(fā)、品牌網(wǎng)站建設

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

猜你還喜歡下面的內(nèi)容