大家都知道，至于迷宮的求解問(wèn)題，可以用窮舉法進(jìn)行求解。那么什么是窮舉法了，就是將每一種可能的情況都窮舉完。而具體到迷宮的求解問(wèn)題上，由于在求解過(guò)程中可能會(huì)遇到某一路徑不可行的情況，此時(shí)我們就必須按原路返回，這時(shí)自然也就會(huì)想到棧的應(yīng)用了，因?yàn)闂５囊粋€(gè)很重要的特性就是”先進(jìn)后出”，可以用來(lái)記錄每次所探索的路徑，方便在原路返回的過(guò)程中，得到上一步所走路徑，再按此方法，退回到可以走得通的位置上，繼續(xù)探索下去，直到到達(dá)終點(diǎn)或者最終無(wú)法到達(dá)，正常退出程序?yàn)橹埂?/p>

創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括豐南網(wǎng)站建設(shè)、豐南網(wǎng)站制作、豐南網(wǎng)頁(yè)制作以及豐南網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(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ù)的客戶以成都為中心已經(jīng)輻射到豐南省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

   下面我們就一起來(lái)探索迷宮！！！

  首先是得到迷宮地圖，這里我們用文件流來(lái)實(shí)現(xiàn)。

void GetMaze(int *a, size_t n)
{
	FILE* fout = fopen("MazeMap.txt", "r");  //打開(kāi)迷宮地圖
	assert(fout);
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 0; j < n;)
		{
			char ch = fgetc(fout);  //讀取一個(gè)字符
			if (ch == '0' || ch == '1')
			{
				a[i*n + j] = ch - '0';
				j++;
			}
			else
			{
				continue;
			}
		}
	}
	fclose(fout);
}

給出迷宮地圖：

0為通路，1為墻

 然后我們將迷宮打印出來(lái)

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

 接著定義位置結(jié)構(gòu)體，用此結(jié)構(gòu)體表示當(dāng)前位置的橫縱坐標(biāo)

struct Pos
{
	int _row;
	int _col;
};

 然后再?gòu)慕o定的入口位置開(kāi)始對(duì)此位置的上下左右四個(gè)相鄰位置進(jìn)行判斷，若為1則行不通，若為0，則可以走，，并將此位置進(jìn)行壓棧。將走過(guò)的位置改為2，以備在回退的時(shí)候可以用

bool MazePath(int* a, size_t n, Pos& entry, stack<Pos>& path)
{
	Pos cur = entry;
	path.push(cur);    //當(dāng)前位置壓棧
	while (!path.empty())
	{
		a[cur._row *n + cur._col] = 2;   //走過(guò)的位置標(biāo)記為2
		Pos next = cur; //將當(dāng)前位置進(jìn)行標(biāo)記
		//上
		next._row--;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		//右
		next = cur;
		next._col++;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		   //下
		next = cur;
		next._row++;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		  //左
		next = cur;
		next._col--;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		 //上下左右都走不通，回退
		cur = path.top();  
		path.pop();
		if (cur._row == n - 1)   // 出口
		{
			return true;
		}
	}
	return false;
}

判斷當(dāng)前位置的下一步是否走得通

bool CheckIsAccess(int* a, size_t n, Pos next)
{
	assert(a);
	if ((next._col >= 0) && (next._col < n) && (next._row >= 0) && (next._row < n) &&
		(a[next._row *n + next._col] == 0))
	{
		return true;
	}
	else
		return false;
}

這樣一個(gè)簡(jiǎn)單的迷宮就完成了，是不是看起來(lái)挺容易的呢？如果有不懂得地方，歡迎留言。有高見(jiàn)也歡迎留言~

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)頁(yè)標(biāo)題：棧----迷宮（Maze）-創(chuàng)新互聯(lián)
標(biāo)題來(lái)源：http://www.chinadenli.net/article34/dcigpe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、網(wǎng)站建設(shè)、ChatGPT、網(wǎng)站制作、域名注冊(cè)、軟件開(kāi)發(fā)

廣告

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