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

標籤

2010年9月25日 星期六

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


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


電腦模擬迷宮說明 :
在建立迷宮前, 我們先來了解如何在電腦中表現一個模擬迷宮的方式. 這時我們可以利用二維矩陣 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 代碼 :
  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 代碼 :
  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. }  
* 呼叫使用演算法代碼 :
  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 :
  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
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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!