最近剛開始學(xué)數(shù)據(jù)結(jié)構(gòu),發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)真是個神奇的東西哈,很多現(xiàn)實中的問題都可以用不同的數(shù)據(jù)結(jié)
創(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ù)獲得客戶的支持與信任!
構(gòu)來解決,比如利用和棧中綴表達式編寫一個計算機程序,利用棧破解迷宮游戲,今天我就來跟大家分
享一下如何利用棧來破解迷宮游戲。
學(xué)過數(shù)據(jù)結(jié)構(gòu)的人都知道,棧的特點是:后進先出(First In Last Out);也就是說只能在棧的尾部進
行壓棧和出棧,而且出棧的時候只能從最后一個數(shù)據(jù)開始。如下圖:
而我們在破解迷宮游戲的時候采用的方法是“回溯”,也就是在尋找通路的時候,每找到一個通路,就將這個數(shù)據(jù)壓棧,這樣當(dāng)前位置的上一個位置就位于棧的頂部,假如當(dāng)前位置的上下左右都找不到通路的時候,就開始回溯,也就是開始從來的路往回走,而之前走過的路都存在棧里面,所以只需要一個一個的Pop就能依次往回退,每退一次,就尋找上下左右有沒有通路,如果找到通路就繼續(xù)往下走,并壓棧,直到走出整個迷宮。大概思路就是這樣啦
首先要如何構(gòu)建一個迷宮呢,如果手動在程序中輸入的話,比較麻煩而且不夠靈活,所以我們可以先將迷宮寫到一個文件里,然后在程序中去讀文件,這樣就ok辣。如下圖
接下來呢我們就要在文件里面去讀這個迷宮咯,具體的代碼:
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; //讀到空格時不進行轉(zhuǎn)換 } else { continue; } } } fclose(fout); }
讀完迷宮之后就要開始尋找同路啦,從入口開始以此判斷上左右是否為空,為了看起來比較直觀,我們
要先寫一個檢查是否有通路的函數(shù),然后再往下走,具體代碼如下:
bool CheckAccess(int *a, int n, pos& next) { if (next.row>0 || next.row<n || next.col>0 || next.col < n || //保證每個位置的有效性 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; //將之前走過的位置保存起來 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; }
以上便是棧破解迷宮的方法,其實這個代碼寫的并不好,還有很多許多地方需要改進和優(yōu)化,比如如何找到最短路徑等,希望讀者們能積極為我指出來,一起相互學(xué)習(xí),共同進步。
當(dāng)前名稱:數(shù)據(jù)結(jié)構(gòu)應(yīng)用:利用棧破解迷宮游戲
文章來源:http://bm7419.com/article10/gihedo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供自適應(yīng)網(wǎng)站、App開發(fā)、網(wǎng)頁設(shè)計公司、軟件開發(fā)、企業(yè)網(wǎng)站制作、移動網(wǎng)站建設(shè)
聲明:本網(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)