大家都知道，至于迷宮的求解問題，可以用窮舉法進行求解。那么什么是窮舉法了，就是將每一種可能的情況都窮舉完。而具體到迷宮的求解問題上，由于在求解過程中可能會遇到某一路徑不可行的情況，此時我們就必須按原路返回，這時自然也就會想到棧的應(yīng)用了，因為棧的一個很重要的特性就是”先進后出”，可以用來記錄每次所探索的路徑，方便在原路返回的過程中，得到上一步所走路徑，再按此方法，退回到可以走得通的位置上，繼續(xù)探索下去，直到到達(dá)終點或者最終無法到達(dá)，正常退出程序為止。

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

   下面我們就一起來探索迷宮?。?！

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

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

給出迷宮地圖：

0為通路，1為墻

 然后我們將迷宮打印出來

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

 然后再從給定的入口位置開始對此位置的上下左右四個相鄰位置進行判斷，若為1則行不通，若為0，則可以走，，并將此位置進行壓棧。將走過的位置改為2，以備在回退的時候可以用

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;   //走過的位置標(biāo)記為2
		Pos next = cur; //將當(dāng)前位置進行標(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;
}

這樣一個簡單的迷宮就完成了，是不是看起來挺容易的呢？如果有不懂得地方，歡迎留言。有高見也歡迎留言~

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

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

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

廣告

聲明：本網(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)