溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
C++ 自定義棧實(shí)現(xiàn)迷宮求解
一：迷宮求解
是一個(gè)鍛煉我們的算法求解能力的問題，它的實(shí)現(xiàn)方法有很多；今天我們就介紹其中的用棧求解的方法。
二：什么是棧：
大家應(yīng)該都有往袋子里裝東西的經(jīng)歷，在往袋子里裝滿東西之后，當(dāng)我們?nèi)ト〉臅r(shí)候，總是先從最后放進(jìn)去的東西的地方去取。也就是后進(jìn)先出(FILO)。雖然棧的單向性用起來會(huì)沒有鏈表那樣可以在任意位置對(duì)數(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)對(duì)路徑的查找
// 通過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)*/
//功能：通過對(duì)棧實(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é)果截圖如下：
其中* 為路徑
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼