最近剛開始學(xué)數(shù)據(jù)結(jié)構(gòu)，發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)真是個(gè)神奇的東西哈，很多現(xiàn)實(shí)中的問題都可以用不同的數(shù)據(jù)結(jié)
構(gòu)來解決，比如利用和棧中綴表達(dá)式編寫一個(gè)計(jì)算機(jī)程序，利用棧破解迷宮游戲，今天我就來跟大家分
享一下如何利用棧來破解迷宮游戲。
學(xué)過數(shù)據(jù)結(jié)構(gòu)的人都知道，棧的特點(diǎn)是：后進(jìn)先出（First In Last Out）;也就是說只能在棧的尾部進(jìn)
行壓棧和出棧，而且出棧的時(shí)候只能從最后一個(gè)數(shù)據(jù)開始。如下圖：
而我們?cè)谄平饷詫m游戲的時(shí)候采用的方法是“回溯”，也就是在尋找通路的時(shí)候，每找到一個(gè)通路，就將這個(gè)數(shù)據(jù)壓棧，這樣當(dāng)前位置的上一個(gè)位置就位于棧的頂部，假如當(dāng)前位置的上下左右都找不到通路的時(shí)候，就開始回溯，也就是開始從來的路往回走，而之前走過的路都存在棧里面，所以只需要一個(gè)一個(gè)的Pop就能依次往回退，每退一次，就尋找上下左右有沒有通路，如果找到通路就繼續(xù)往下走，并壓棧，直到走出整個(gè)迷宮。大概思路就是這樣啦
首先要如何構(gòu)建一個(gè)迷宮呢，如果手動(dòng)在程序中輸入的話，比較麻煩而且不夠靈活，所以我們可以先將迷宮寫到一個(gè)文件里，然后在程序中去讀文件，這樣就ok辣。如下圖
接下來呢我們就要在文件里面去讀這個(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);
}讀完迷宮之后就要開始尋找同路啦，從入口開始以此判斷上左右是否為空，為了看起來比較直觀，我們
要先寫一個(gè)檢查是否有通路的函數(shù)，然后再往下走，具體代碼如下：
bool CheckAccess(int *a, int n, pos& next)
{
if (next.row>0 || next.row0 || 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 path)
{
pos cur = entry;
path.push(cur);
while (!path.empty())
{
if (cur.row == n - 1)
{
return true;
}
a[cur.row*n + cur.col] = 2; //將之前走過的位置保存起來
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;
}
下面我們可以將迷宮打印出來了：
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è)代碼寫的并不好，還有很多許多地方需要改進(jìn)和優(yōu)化，比如如何找到最短路徑等，希望讀者們能積極為我指出來，一起相互學(xué)習(xí)，共同進(jìn)步。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+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)景需求。
