歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

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

/***********程序設計思想*************/
(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,繼續遞歸,

Copyright © Linux教程網 All Rights Reserved