最近剛開(kāi)始學(xué)數(shù)據(jù)結(jié)構(gòu)，發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)真是個(gè)神奇的東西哈，很多現(xiàn)實(shí)中的問(wèn)題都可以用不同的數(shù)據(jù)結(jié)

創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括和田縣網(wǎng)站建設(shè)、和田縣網(wǎng)站制作、和田縣網(wǎng)頁(yè)制作以及和田縣網(wǎng)絡(luò)營(yíng)銷(xiāo)策劃等。多年來(lái)，我們專(zhuān)注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，和田縣網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶(hù)以成都為中心已經(jīng)輻射到和田縣省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶(hù)的支持與信任！

構(gòu)來(lái)解決，比如利用和棧中綴表達(dá)式編寫(xiě)一個(gè)計(jì)算機(jī)程序，利用棧破解迷宮游戲，今天我就來(lái)跟大家分

享一下如何利用棧來(lái)破解迷宮游戲。

學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的人都知道，棧的特點(diǎn)是：后進(jìn)先出（First In Last Out）;也就是說(shuō)只能在棧的尾部進(jìn)

行壓棧和出棧，而且出棧的時(shí)候只能從最后一個(gè)數(shù)據(jù)開(kāi)始。如下圖：

而我們?cè)谄平饷詫m游戲的時(shí)候采用的方法是“回溯”，也就是在尋找通路的時(shí)候，每找到一個(gè)通路，就將這個(gè)數(shù)據(jù)壓棧，這樣當(dāng)前位置的上一個(gè)位置就位于棧的頂部，假如當(dāng)前位置的上下左右都找不到通路的時(shí)候，就開(kāi)始回溯，也就是開(kāi)始從來(lái)的路往回走，而之前走過(guò)的路都存在棧里面，所以只需要一個(gè)一個(gè)的Pop就能依次往回退，每退一次，就尋找上下左右有沒(méi)有通路，如果找到通路就繼續(xù)往下走，并壓棧，直到走出整個(gè)迷宮。大概思路就是這樣啦

首先要如何構(gòu)建一個(gè)迷宮呢，如果手動(dòng)在程序中輸入的話(huà)，比較麻煩而且不夠靈活，所以我們可以先將迷宮寫(xiě)到一個(gè)文件里，然后在程序中去讀文件，這樣就ok辣。如下圖

接下來(lái)呢我們就要在文件里面去讀這個(gè)迷宮咯，具體的代碼：

void GetMaze(int *a, int n)
{
	FILE* fout = fopen("Maze Map.txt", "r");
	assert(fout);
	for (int i = 0; i < n;i++)
	{
		for (int j = 0; j < n;)
		{
			char ch = fgetc(fout);
			if (ch == '0' || ch == '1')
			{
				a[i*n + j] = ch - '0';
				++j;                   //讀到空格時(shí)不進(jìn)行轉(zhuǎn)換
			}
			else
			{
				continue;
			}
		}
	}
	fclose(fout);
}

讀完迷宮之后就要開(kāi)始尋找同路啦，從入口開(kāi)始以此判斷上左右是否為空，為了看起來(lái)比較直觀，我們

要先寫(xiě)一個(gè)檢查是否有通路的函數(shù)，然后再往下走，具體代碼如下：

bool CheckAccess(int *a, int n, pos& next)
{
	if (next.row>0 || next.row<n || next.col>0 || next.col < n ||   //保證每個(gè)位置的有效性
		a[next.row*n + next.col] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
bool MazePath(int* a, int n, pos& entry,stack<pos> path)
{
	pos cur = entry;
	path.push(cur);
	
	while (!path.empty())
	{
		if (cur.row == n - 1)
		{
			return true;
		}
		a[cur.row*n + cur.col] = 2;   //將之前走過(guò)的位置保存起來(lái)
		pos next = cur;
		next.row--;                   //上路
		if (CheckAccess(a,n,next))
		{
			next=cur;
			path.push(cur);
			continue;
		}
		next.row++;                  //下路
		if (CheckAccess(a, n, next))
		{
			next=cur;
			path.push(cur);
			continue;
		}
		next.col--;                //左路
		if (CheckAccess(a, n, next))
		{
			next= cur;
			path.push(cur);
			continue;
		}
		next.col++;                //右路
		if (CheckAccess(a, n, next))
		{
			next = cur;
			path.push(cur);
			continue;
		}
           cur = path.top();
	       path.pop();
       }
	return false;
	}
	

下面我們可以將迷宮打印出來(lái)了：

void PrintMaze(int *a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << a[i*n + j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

以上便是棧破解迷宮的方法，其實(shí)這個(gè)代碼寫(xiě)的并不好，還有很多許多地方需要改進(jìn)和優(yōu)化，比如如何找到最短路徑等，希望讀者們能積極為我指出來(lái)，一起相互學(xué)習(xí)，共同進(jìn)步。

當(dāng)前名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)應(yīng)用：利用棧破解迷宮游戲
文章來(lái)源：http://aaarwkj.com/article10/gihedo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、App開(kāi)發(fā)、網(wǎng)頁(yè)設(shè)計(jì)公司、軟件開(kāi)發(fā)、企業(yè)網(wǎng)站制作、移動(dòng)網(wǎng)站建設(shè)

廣告

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