數據結構之棧的應用----迷宮求解

/***********程序設計思想*************/
（1）迷宮地圖相關：
利用動態二維數組來初步勾勒出迷宮：
建議先用malloc申請一維數組，再用calloc申請每個元素中的一維數組，因為我用的是1來表示迷宮的通路，0表示死路，calloc申請完後就會自動初始化為0
迷宮交岔路結點：
我們要有一個掃描通路的函數，對一個坐標進行東南西北的掃描，當遇到交岔路的坐標時，需要將所有的通路存入一個數組，掃描從東開始，至北結束，逆時針方向
這裡設計的是單通道迷宮，也就是說不會有並行的通路，掃描出來的通路是不會超過兩個的（肯定是不允許把結點來的那個原始方向認為是通路的）
當我們按著第一個方向走到死路時，我們需要返回到最近的一個交岔路結點，這之後第一個最重要的操作便是：將已確定的死路給封死，即把那個坐標的值從1改為0。
（2）棧相關：
棧在這裡需要兩個，一個存放走過的路徑，也就是移動到一個坐標，就把這個坐標入棧，另一個是存放交岔路結點的，當我們遇到死路之後，就需要從交岔路結點棧中
彈出一個元素A，然後從所有路徑的棧中一直彈出元素（就是原路返回），直到棧頂元素B與A相等，就表明已經退回到了最近的一個交岔路口
下一步便是走向另一個通路，直到遇到死路或終點
（3）設計根本：
整個程序是建立在遞歸應用中的，抽象出來就是：當我們規定一個優先方向（默認為東方向吧）、再規定一個固定的旋轉方向（默認為逆時針）之後，我們會有一個從東方、
沿逆時針、到北方的總體走向，遇到一個死胡同，我們就要沿著路徑原路返回，直到遇到一個十字路口，再走向另一個可通的方向，要是還是死胡同，就返回到再前一個十字
路口，進入另一個可通的方向，如此反復的探索，知道走到終點。
/***********程序設計細節*************/
（1）掃描通道函數----int Scan_Direction(data_type elem,int *all_direction,int **labyrinth);
返回值：返回所有可通方向的數量，可能值為0，1，2
重要參數：all_direction：記錄所有可通的方向
關鍵實現：

1. if(labyrinth[elem.x][elem.y+1] == YES && elem.direction != EAST)
2. {
3. direction = EAST;
4. all_direction[i++] = EAST;
5. }

坐標是按照二維數組的行列來規定的，這裡給出的是判斷當前坐標的東向是可通，YES表明可通，當坐標的東鄰坐標（[elem.x][elem.y+1]）值為YES的時候，我們並不能
確定它的東方向就是可通的，因為有一種例外：當這個坐標就是從它的東鄰坐標移過來的時候，這個坐標當然是可通的，所以在if的判斷語句中還應加上一個判斷語句：
elem.direction != EAST，只有當這兩個條件同時滿足的時候才表明東鄰為通，其余三個方向的判斷與之類似

（2）根據方向的數目來走迷宮

case 1：先看只有一個方向可走到時候

這種情況很好解決，按著掃描的方向走一步就OK，讓移動後的坐標入棧即可，這裡我遇到了一個小問題，就是由於很多次的往回走，每一次都要入棧或出棧，貌似這樣可能

造成路徑棧中存在幾個相同的坐標，並且這些坐標在棧中都是相鄰的，所以我在每次入棧的時候都判斷了一下，如果和棧頂元素相同，就不入棧了，以免最後彈出正確路徑的

時候出現多個重復的坐標

case 2：這個條件是程序的關鍵部分，總的來說就是先走一個方向，若未遇到終點，就返回到交岔路結點，再走向另一條路，反復直到走到終點

1. case 2:
2. {
3. Push_Stack(&cross_point,position);
4. GetElem_Stack(&path,&top_path);
5. if(top_path.x != position.x || top_path.y != position.y)
6. Push_Stack(&path,position);
7. Print_Position(position);
8. Move_Path(&position,all_direction[0],&path,&cross_point,labyrinth);
9. if(position.x == (LINE-2) && position.y == (ROW-2))
10. break;
11. Move_Path(&position,all_direction[1],&path,&cross_point,labyrinth);
12. }
13. break;

首先讓交岔路結點入棧（交叉點棧），讓這個點入路徑棧

接下來就是走向第一個方向，進入這個方向後，position將先通過all_direction[0]方向移動一格，然後利用遞歸，對新坐標進行掃描，判斷出可通方向個數（0，1，2三種），

接著就開始重復昨天的故事，也就是遞歸了，當這一個方向走完後，這個Move_Path就結束了，然後判斷是否到了終點，如果不是終點就進入第二個Move_Path，繼續遞歸，