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

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

這個用到了一些C++的知識了，因為需要用到動態建立數組和類的一些知識。

以前遇到類似的問題就很頭疼，而且也不願意去寫，可是現在覺得只要肯花時間，

寫起來並不那麼困難，雖然一次性完美的寫出來，不出錯不可能，但是在調試錯誤的過程中同樣能感覺到快樂。

考慮到節約時間，我就隨機生成了一個地圖，矩陣的大小可以輸入。1為可走，0為走不通。

代碼並沒有完善到我想要的目的，例如目前只能尋找一條路線，多條路線還沒有思路。

代碼的主要思想就是壓棧和出棧

/*************************************************************************
    > File Name: maze.cpp
    > Author: Darin
    > Mail: [email protected] 
    > Created Time: 2013年06月08日 星期四 06時36分24秒
 ************************************************************************/
#include <iostream>
#include <stdlib.h> 
#include <time.h>
using namespace std;
#define orientationNum 4
int MazeMapLineNumber = 0;
typedef struct Position {
    int xcoordinate;
    int ycoordinate;
}POSITION;

typedef struct Node {
    POSITION Pos;
    struct Node *pNext;
}NODE,*PNode;

class CStack {
    public: 
        PNode pTop;
        PNode pBottom;
    public: 
            CStack();
            bool IsNull();
            void Push(POSITION pos);
            void Pop();
            POSITION GetTop();
            void clear();
            void ShowWay();
            ~CStack();
};

CStack::CStack(){
    pTop = pBottom = new NODE;
    pTop->pNext = NULL;
}

bool CStack::IsNull() {
    if (pTop == pBottom)
        return true;
    return false;
}

void CStack::Push(POSITION pos) {
    PNode p = new NODE;
    p->Pos = pos;
    p->pNext = pTop;
    pTop= p;
}

void CStack::Pop(){
    if(!IsNull()) {
        PNode p = pTop;
        pTop = p->pNext;
        delete(p);
    } else cout<<"The stack is null "<<endl;
}

void CStack::ShowWay() {
    PNode p = pTop;
    while(p->pNext != pBottom) {
        cout<<"("<<p->Pos.xcoordinate<<","<<p->Pos.ycoordinate<<") -> ";
        p = p->pNext;
    }
    cout<<"("<<p->Pos.xcoordinate<<","<<p->Pos.ycoordinate<<")";
}

POSITION CStack::GetTop() {
    return pTop->Pos;
}

void CStack::clear() {
    while(!IsNull()) Pop();
}

CStack::~CStack() {
    clear();
}
bool isOutOfborder(POSITION pos) {
    if(pos.ycoordinate<0 || pos.ycoordinate>=MazeMapLineNumber
        ||pos.xcoordinate<0 || pos.xcoordinate>=MazeMapLineNumber)
        return true;
    return false;
}

bool isequal(POSITION pos1,POSITION pos2) {
    if(pos1.xcoordinate == pos2.xcoordinate && 
        pos1.ycoordinate == pos2.ycoordinate) return true;
    return false;
}

void PassMaze(int **map,POSITION Inpos,POSITION OutPos) {
    CStack *MazeWay = new CStack();
    POSITION CurPos = OutPos;
    POSITION NewPos;
    int i =0;
    bool IsFind = false;
    MazeWay->Push(CurPos);
    while((!MazeWay->IsNull())&&(!isequal(CurPos,Inpos))) {
        //(!isOutOfborder(CurPos))
        CurPos = MazeWay->GetTop();
        IsFind = false;
        for(i=0;i<orientationNum;i++) {
            if(0 == i) {
                //right
                NewPos.xcoordinate = CurPos.xcoordinate;
                NewPos.ycoordinate = CurPos.ycoordinate+1;
            }
            if(1 == i) {
                //down
                NewPos.xcoordinate = CurPos.xcoordinate+1;
                NewPos.ycoordinate = CurPos.ycoordinate;
            }
            if(2 == i) {
                //left
                NewPos.xcoordinate = CurPos.xcoordinate;
                NewPos.ycoordinate = CurPos.ycoordinate-1;
            }
            if(3 == i) {
                //up
                NewPos.xcoordinate = CurPos.xcoordinate-1;
                NewPos.ycoordinate = CurPos.ycoordinate;
            }

            if(!isOutOfborder(NewPos) && map[NewPos.xcoordinate][NewPos.ycoordinate]) {
                IsFind = true;
                CurPos = NewPos;
                map[NewPos.xcoordinate][NewPos.ycoordinate] = 0;
                break;
            }
        }
        if(IsFind) {
            MazeWay->Push(CurPos);
        } else MazeWay->Pop();

    }
    if(MazeWay->IsNull()) {
        cout<<"There is no way to go out of the maze"<<endl;
    } else MazeWay->ShowWay();
}

int main() {
    int i=0,j=0;
    srand((unsigned)time(NULL));
    cout<<"Please input the row of the maze map:";
    cin>>MazeMapLineNumber;
    POSITION inpos;
    POSITION outpos;

    int **pMap = new int *[MazeMapLineNumber];
    for (i=0;i<MazeMapLineNumber;i++) {
        pMap[i] = new int [MazeMapLineNumber];
    }

    for (i=0;i<MazeMapLineNumber;i++) {
        for (j=0;j<MazeMapLineNumber;j++) {
            pMap[i][j] = rand()%2;
            cout<<pMap[i][j]<<" ";
        }
        cout<<"\n";
    }

//     for (i=0;i<MazeMapLineNumber;i++) {
//         for (j=0;j<MazeMapLineNumber;j++) {
//             cout<<pMap[i][j]<<" ";
//         }
//         cout<<"\n";
//     }

    cout<<"Please input inpos.x :";
    cin>>inpos.xcoordinate;
    cout<<"Please input inpos.y :";
    cin>>inpos.ycoordinate;
    cout<<"Please input outpos.x :";
    cin>>outpos.xcoordinate;
    cout<<"Please input outpos.y :";
    cin>>outpos.ycoordinate;
    PassMaze(pMap,inpos,outpos);
    
    return 0;
}