C++ 自定義棧實(shí)現(xiàn)迷宮求解

更新時(shí)間：2017年07月05日 10:22:17 投稿：lqh

這篇文章主要介紹了C++ 自定義棧實(shí)現(xiàn)迷宮求解的相關(guān)資料,需要的朋友可以參考下

C++ 自定義棧實(shí)現(xiàn)迷宮求解

一：迷宮求解

是一個(gè)鍛煉我們的算法求解能力的問題，它的實(shí)現(xiàn)方法有很多；今天我們就介紹其中的用棧求解的方法。

二：什么是棧：

大家應(yīng)該都有往袋子里裝東西的經(jīng)歷，在往袋子里裝滿東西之后，當(dāng)我們?nèi)ト〉臅r(shí)候，總是先從最后放進(jìn)去的東西的地方去取。也就是后進(jìn)先出(FILO)。雖然棧的單向性用起來會沒有鏈表那樣可以在任意位置對數(shù)據(jù)進(jìn)行操作，但是正因?yàn)槿绱藯Ｒ矌砹撕艽蟮姆奖恪?br />

三：迷宮求解

現(xiàn)在我們要在下面的迷宮尋找一條可行的路徑

 1 1 1 1 1 1 1 1 1 1
 1 0 0 1 1 0 0 0 0 1
 1 0 0 0 1 0 1 0 0 1
 1 0 1 0 0 0 1 1 0 1
 1 0 1 0 0 0 1 1 1 1
 1 0 1 1 1 0 1 1 1 1
 1 0 1 1 1 0 1 1 1 1
 1 1 1 1 1 0 0 0 1 1
 1 1 1 1 1 1 1 0 0 1
 1 1 1 1 1 1 1 1 1 1

首先我們需要在程序中表示上面的迷宮，該問題可以用數(shù)組實(shí)現(xiàn)

1：棧的定義

/************************************************************************/ 
/*自定義棧                                     */ 
/*通過自定義的簡單棧以滿足迷宮求解        */ 
/*功能：push() 將元素加入棧中                 */ 
/*        pop() 退棧；topValue() 獲得棧頂元素    */ 
/*        clear() 清除棧 length() 獲得棧中元素個(gè)數(shù)*/ 
/************************************************************************/ 
#include <stack> 
#include <iostream> 
using namespace std; 
 
template<typename Elem> class PathStack: public stack<Elem> 
{ 
private: 
  int size; 
  int top; 
  Elem* listArray; 
public: 
  PathStack(int sz = DefaultListSize){ 
    size = sz; 
    top = 0; 
    listArray = new Elem[sz]; 
  } 
  ~PathStack(){ delete []listArray; } 
  void clear(){ top = 0; } 
  /****向棧中加入元素****/ 
  bool push(const Elem& item); 
  /***********退棧**********/ 
  Elem pop(); 
  /********獲得棧頂元素*******/ 
  Elem topValue() const; 
  int length() const { return top; } 
}; 
 
template<typename Elem> 
bool PathStack<typename Elem>::push(const Elem& item){ 
  if(top == size) return false; 
  listArray[top++] = item; 
  return true; 
} 
 
template<typename Elem> 
Elem PathStack<typename Elem>::pop(){ 
  Elem it; 
  if(top == 0) return it; 
  it = listArray[--top];  
  return it; 
} 
 
template<typename Elem> 
Elem PathStack<typename Elem>::topValue() const{ 
  Elem it; 
  if(top == 0) return it; 
  it = listArray[top - 1]; 
  return it; 
}

2：如何實(shí)現(xiàn)路徑的尋找

1：設(shè)定尋找的方向，可以使用一個(gè)判斷語句；判斷起始位置周圍哪個(gè)地方有路就將該位置的坐標(biāo)加入到棧中，并將該位置標(biāo)記(將改位置值改為2,既將走過的位置標(biāo)記為2)

2：判斷該位置周圍是否還有路，若沒有則退棧即退回到上一個(gè)位置；并將該位置做下另一個(gè)標(biāo)記(將該位置值改為3,既將退棧位置值用3標(biāo)記)

3：重復(fù)1,2步驟直到達(dá)到出口

路徑尋找的類：

//迷宮求解的方法類 
//功能：通過findPath() 方法實(shí)現(xiàn)對路徑的查找 
//       通過printPath()方法將路徑打印出來 
#include "PathStack.h" 
#include <iostream> 
using namespace std; 
 
class MazeSolveMethod 
{ 
private: 
  static int maze[10][10];//存放迷宮數(shù)據(jù) 
  PathStack<int> pathStack;//定義棧 
public: 
  MazeSolveMethod():pathStack(100){ 
  } 
  ~MazeSolveMethod(){ } 
  void findPath(int startX,int startY); 
  void printPath() const; 
}; 
 
int MazeSolveMethod::maze[10][10] = { 
  {1,1,1,1,1,1,1,1,1,1}, 
  {1,0,0,1,1,0,0,0,0,1}, 
  {1,0,0,0,1,0,1,0,0,1}, 
  {1,0,1,0,0,0,1,1,0,1}, 
  {1,0,1,0,0,0,1,1,1,1}, 
  {1,0,1,1,1,0,1,1,1,1}, 
  {1,0,1,1,1,0,1,1,1,1}, 
  {1,1,1,1,1,0,0,0,1,1}, 
  {1,1,1,1,1,1,1,0,0,1}, 
  {1,1,1,1,1,1,1,1,1,1}, 
}; 
 
void MazeSolveMethod::findPath(int startX,int startY){ 
  int x = startX; 
  int y = startY; 
  pathStack.push(x); 
  pathStack.push(y); 
  maze[x][y] = 2; 
  cout<<"進(jìn)入方法！"<<endl; 
  while(true){ 
    if(maze[x-1][y] == 0){ 
      pathStack.push(--x); 
      pathStack.push(y); 
      maze[x][y] = 2; 
    }else if(maze[x][y-1] == 0){ 
      pathStack.push(x); 
      pathStack.push(--y); 
      maze[x][y] = 2; 
    }else if(maze[x][y+1] == 0){ 
      pathStack.push(x); 
      pathStack.push(++y); 
      maze[x][y] = 2; 
    }else if(maze[x+1][y] == 0){ 
      pathStack.push(++x); 
      pathStack.push(y); 
      maze[x][y] = 2; 
    } 
    if(maze[x-1][y] != 0 && maze[x][y+1] != 0 && maze[x+1][y] != 0 && maze[x][y-1] != 0){         
      if(x >= 8 && y >= 8){ 
        break; 
      }else{ 
        maze[x][y] = 3; 
        y = pathStack.pop(); 
        x = pathStack.pop(); 
      } 
      y = pathStack.topValue(); 
      int temp = pathStack.pop(); 
      x = pathStack.topValue(); 
      pathStack.push(temp); 
    } 
  } 
} 
 
void MazeSolveMethod::printPath() const{ 
  cout<<"printPath"<<endl; 
  for(int i=0; i<10; i++){ 
    for(int j=0; j<10; j++){ 
      if(maze[i][j] == 2) 
        cout<<'*'<<" "; 
      else if(maze[i][j] == 3) 
        cout<<0<<" "; 
      else 
        cout<<1<<" "; 
    } 
    cout<<endl; 
  } 
}

主函數(shù)類

/************************************************************************/ 
/*迷宮求解----棧方法實(shí)現(xiàn)*/ 
//功能：通過對棧實(shí)現(xiàn)迷宮算法求解 
//Author：Andrew 
//Date  ：2012-10-20 
/************************************************************************/ 
#include "MazeSolveMethod.h" 
#include <iostream> 
using std::cout; 
using std::endl; 
 
int main(){ 
 
  MazeSolveMethod solve; 
  solve.findPath(1,1); 
  solve.printPath(); 
  system("pause"); 
  return 0; 
}

將上面的代碼運(yùn)行后結(jié)果截圖如下：

其中* 為路徑