[ 資料結構 小學堂 ] 堆疊 : 堆疊應用 (迷宮問題)

前言 :
老鼠走迷宮是堆疊在實際應用上一個很好的例子. 在一個實驗中, 老鼠被放進一個迷宮裡, 當老鼠走錯路時, 就會重走一次並把走過的路記起來, 避免走重複的路, 就這樣直到找到出口為止. 另外在迷宮移動尋找出口時, 電腦還必須判斷下一步該往哪一個方向移動, 此外還必須記錄能夠走的迷宮路徑, 如此才可以在迷宮走到死胡同時, 可以回頭來搜尋其它路徑. 在迷宮行進, 必須遵守以下三個原則 :

* 一次只能走一格.
* 遇到牆無法往前走時,則退回一步找找看是否有其他的路可以走.
* 走過的路不會再走第二次.

電腦模擬迷宮說明 :
在建立迷宮前, 我們先來了解如何在電腦中表現一個模擬迷宮的方式. 這時我們可以利用二維矩陣 MAZE[row][col], 並符合以下規則 :

* MAZE[i][j] = 1 : 表示[i][j] 處有牆, 無法通過.
* MAZE[i][j] = 0 : 表示[i][j] 處無牆, 可以通過.
* MAZE[1][1] 是入口, MAZE[m-2][n-2] 是出口.

下圖就是一個使用 10x12 二維陣列的模擬迷宮地圖表示圖 :

假設老鼠從左上角的 MAZE[1][1] 進入, 由右下角MAZE[8][10] 出來, 老鼠目前位置以 MAZE[x][y] 表示, 那麼我們可以將老鼠的移動方向表示如下 :

如上圖所示, 老鼠可以選擇的方向共有四個, 分別為東, 南, 西, 北. 但並非每個位置都可以移動, 必須視情況與目前位置來決定. 因此我們可以利用鏈結串列來記錄走過的位置, 並將走過的位置的陣列元素內容標示為 2, 然後將這個位置放入堆疊再進行下一次的選擇. 如果走到死巷子並且還沒走到終點, 那麼就必須退回到上一個位置, 並退回去, 直到回到上一個叉路後再選擇其他路. 由於每次加入新的位置必定會在堆疊的頂端, 因此堆疊頂端所指位置便是目前老鼠所在位置. 如此一直重複直到走到出口為止.

範例代碼 :
* Map.h 代碼 :

view plaincopy to clipboardprint?

1. #ifndef _MAP_FOR_MAZE  
2. #define _MAP_FOR_MAZE  
3. #include   
4.   
5. #define EAST MAZE[x][y+1]  
6. #define WEST MAZE[x][y-1]  
7. #define SOUTH MAZE[x+1][y]  
8. #define NORTH MAZE[x-1][y]  
9.   
10. struct pos{  
11.     int x,y;  
12.     struct pos* next;  
13. };  
14.   
15. typedef struct pos pnode;  
16. typedef pnode* plink;  
17.   
18.   
19. class Map{  
20. public:  
21.     plink curPos;  
22.     Map(){  
23.         curPos = NULL;  
24.     }     
25.     ~Map(){  
26.         //delete all curPos  
27.         while(curPos) {  
28.             plink top = curPos;  
29.             curPos = curPos->next;  
30.             delete top;  
31.         }  
32.     }  
33.     virtual plink push(int x, int y);  
34.     virtual plink pop(int* x, int* y);  
35.     virtual int chkExit(int x,int y,int ex,int ey);  
36. };  
37. #endif  

* Map.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "Map.h"  
2.   
3. plink Map::push(int x, int y) {  
4.     if(curPos==NULL){  
5.         curPos = new pnode;  
6.         curPos->x = x;  
7.         curPos->y = y;  
8.         curPos->next = NULL;  
9.         return curPos;  
10.     } else {  
11.         plink newnode = new pnode;  
12.         newnode->x = x;  
13.         newnode->y = y;  
14.         newnode->next = curPos;  
15.         curPos = newnode;  
16.         return curPos;  
17.     }  
18. }  
19.   
20. plink Map::pop(int* x, int* y){  
21.     if(curPos == NULL){  
22.         *x = -1;  
23.         return NULL;  
24.     } else {  
25.         plink top = curPos;  
26.         *x = curPos->x;  
27.         *y = curPos->y;  
28.         curPos = curPos->next;  
29.         delete top;  
30.         return curPos;  
31.     }  
32. }  
33.   
34. int Map::chkExit(int x, int y, int ex, int ey){  
35.     if(x==ex && y==ey){  
36.         return 1;  
37.     } else {  
38.         return 0;  
39.     }  
40. }  

* 呼叫使用演算法代碼 :

view plaincopy to clipboardprint?

1. const int ExitX = 8;  
2. const int ExitY = 10;  
3. int MAZE[10][12] = {1,1,1,1,1,1,1,1,1,1,1,1,  
4.                               1,0,0,0,1,1,1,1,1,1,1,1,  
5.                               1,1,1,0,1,1,0,0,0,0,1,1,  
6.                               1,1,1,0,1,1,0,1,1,0,1,1,  
7.                               1,1,1,0,0,0,0,1,1,0,1,1,  
8.                               1,1,1,0,1,1,0,1,1,0,1,1,  
9.                               1,1,1,0,1,1,0,1,1,0,1,1,  
10.                               1,1,1,1,1,1,0,1,1,0,1,1,  
11.                               1,1,0,0,0,0,0,0,1,0,0,1,  
12.                               1,1,1,1,1,1,1,1,1,1,1,1};  
13.   
14. void ch04_07(bool b) {  
15.     if(b) {       
16.         int x=1, y=1;  
17.         plink path = NULL;  
18.         Map map;  
19.         cout << "[列印出迷宮路徑]" << endl;  
20.         for(int i=0; i<10; i++) {  
21.             for(int j=0;j<12; j++)  
22.                 cout << MAZE[i][j] << " ";  
23.             cout << endl;  
24.         }  
25.         // 開始走迷宮  
26.         while(x<=ExitX && y<=ExitY){  
27.             MAZE[x][y] = 2;  
28.             if(NORTH==0) {  
29.                 x-=1;  
30.                 path = map.push(x,y);  
31.             } else if(SOUTH==0) {  
32.                 x+=1;  
33.                 path = map.push(x,y);  
34.             } else if(WEST==0) {  
35.                 y-=1;  
36.                 path = map.push(x,y);  
37.             } else if(EAST==0) {  
38.                 y+=1;  
39.                 path = map.push(x,y);  
40.             } else if(map.chkExit(x,y,ExitX,ExitY)==1){  
41.                 cout << "\t>>> 走出迷宮!" << endl;  
42.                 break;  
43.             } else { // 走到死胡同  
44.                 MAZE[x][y] = 2;  
45.                 path = map.pop(&x, &y);  
46.             }  
47.         }  
48.         cout << "[列印出迷宮路徑]" << endl;  
49.         for(int i=0; i<10; i++) {  
50.             for(int j=0;j<12; j++)  
51.                 cout << MAZE[i][j] << " ";  
52.             cout << endl;  
53.         }  
54.     }  
55. }  

執行函式 ch04_07 結果 :

[列印出迷宮路徑]
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 0 0 0 1 1
1 1 1 0 1 1 0 1 1 0 1 1
1 1 1 0 0 0 0 1 1 0 1 1
1 1 1 0 1 1 0 1 1 0 1 1
1 1 1 0 1 1 0 1 1 0 1 1
1 1 1 1 1 1 0 1 1 0 1 1
1 1 0 0 0 0 0 0 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
>>> 走出迷宮!
[列印出迷宮路徑]
1 1 1 1 1 1 1 1 1 1 1 1
1 2 2 2 1 1 1 1 1 1 1 1
1 1 1 2 1 1 2 2 2 2 1 1
1 1 1 2 1 1 2 1 1 2 1 1
1 1 1 2 2 2 2 1 1 2 1 1
1 1 1 2 1 1 0 1 1 2 1 1
1 1 1 2 1 1 0 1 1 2 1 1
1 1 1 1 1 1 0 1 1 2 1 1
1 1 0 0 0 0 0 0 1 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1 <數字2為老鼠走過路徑>

範例代碼 (java) :

- Maze.java :

view plaincopy to clipboardprint?

1. package DSwJ.S14.apps;  
2.   
3. import DSwJ.S14.ALStack;  
4.   
5. public class Maze {  
6.     public static final int ExitX = 10;    
7.     public static final int ExitY = 8;  
8.     public int curX=1;  
9.     public int curY=1;  
10.     protected ALStack history;             
11.     private int[][] MAZE = {{1,1,1,1,1,1,1,1,1,1,1,1},    
12.                             {1,0,0,0,1,1,1,1,1,1,1,1},    
13.                             {1,1,1,0,1,1,0,0,0,0,1,1},    
14.                             {1,1,1,0,1,1,0,1,1,0,1,1},    
15.                             {1,1,1,0,0,0,0,1,1,0,1,1},    
16.                             {1,1,1,0,1,1,0,1,1,0,1,1},    
17.                             {1,1,1,0,1,1,0,1,1,0,1,1},    
18.                             {1,1,1,1,1,1,0,1,1,0,1,1},    
19.                             {1,1,0,0,0,0,0,0,1,0,0,1},    
20.                             {1,1,1,1,1,1,1,1,1,1,1,1}};  
21.       
22.     public Maze() {history = new ALStack();}  
23.       
24.     public boolean start(){  
25.         go(curX,curY);  
26.         while(true) {             
27.             if(north()==0){  
28.                 goNorth();  
29.             } else if(south()==0) {  
30.                 goSouth();  
31.             } else if(west()==0) {  
32.                 goWest();  
33.             } else if(east()==0) {  
34.                 goEast();  
35.             } else {  
36.                 Pos backPos = back();  
37.                 if(backPos==null){  
38.                     System.out.println("Exit is unreachable!!!");  
39.                     return false;                     
40.                 } else {  
41.                     curX = backPos.getX();  
42.                     curY = backPos.getY();  
43.                 }  
44.             }  
45.             if(isExit())return true;;  
46.         }  
47.     }  
48.       
49.     public int north(){return MAZE[curY-1][curX];}  
50.     public int south(){return MAZE[curY+1][curX];}  
51.     public int west(){return MAZE[curY][curX-1];}  
52.     public int east(){return MAZE[curY][curX+1];}  
53.       
54.     public void goNorth(){go(curX,--curY);}  
55.     public void goSouth(){go(curX,++curY);}  
56.     public void goEast(){go(++curX,curY);}  
57.     public void goWest(){go(--curX,curY);}  
58.     public void go(int x, int y) {  
59.         MAZE[y][x]=2;  
60.         history.push(new Pos(x,y));  
61.     }  
62.       
63.     public Pos back(){  
64.         return history.pop();  
65.     }  
66.       
67.     public boolean isExit(){if(curX==ExitX&&curY==ExitY)return true;return false;}  
68.       
69.     public void showMaze(){  
70.         for(int i=0; i
71.             for(int j=0; j
72.                 System.out.print(MAZE[i][j]+" ");  
73.             System.out.println();  
74.         }  
75.     }  
76.       
77.     public static void main(String args[]) {  
78.         Maze maze = new Maze();  
79.         if(maze.start()) {  
80.             System.out.println("Conquer the maze ^^.");  
81.         } else {  
82.             System.out.println("I lost in the maze ==\".");  
83.         }  
84.         maze.showMaze();  
85.     }  
86. }  

執行結果 :

Conquer the maze ^^.
1 1 1 1 1 1 1 1 1 1 1 1
1 2 2 2 1 1 1 1 1 1 1 1
1 1 1 2 1 1 2 2 2 2 1 1
1 1 1 2 1 1 2 1 1 2 1 1
1 1 1 2 2 2 2 1 1 2 1 1
1 1 1 2 1 1 0 1 1 2 1 1
1 1 1 2 1 1 0 1 1 2 1 1
1 1 1 1 1 1 0 1 1 2 1 1
1 1 0 0 0 0 0 0 1 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1