【DS 】 迷宫问题 栈与递归

template<class Type>
class Stack
{
    public:
        Stack()
        {
            capacity = STACK_SIZE;
            base = new Type[capacity];
            top = 0;
        }
        ~Stack()
        {
            capacity = 0;
            delete []base;
            base = NULL;
            top = 0;
        }
    public:
        bool isfull()const
        {
            return top >= capacity;
        }
        bool isempty()const
        {
            return top == 0;
        }
        void push(Type &x)
        {
            if(!isfull())
            {
                base[top++] = x;
            }
        }
        void pop()
        {
            if(!isempty())
            {
                top--;
            }
        }
        Type gettop()const
        {
            if(!isempty())
            {
                return base[top-1];
            }
        }
    private:
        enum{STACK_SIZE=100};
        Type *base;
        size_t top;
        size_t capacity;
};

/////////////////////////////////////////////
#define ROW 10
#define COL 10

typedef enum
{
    RIGHT=1,
    DOWN,
    LEFT,
    UP,
}DIR;

typedef int Maze[ROW][COL];//
typedef struct Pos
{
    int x;
    int y;
    bool operator==(const Pos &p)
    {
        return ((x==p.x)&&(y==p.y));
    }
}Pos;

typedef struct Man
{
    Pos pos;
    DIR di;
}Man;


void ShowMaze(Maze maze)
{
    for(int i=0; i<10; ++i)
    {
        for(int j=0; j<10; ++j)
        {
            cout<<maze[i][j]<<" ";
        }
        cout<<endl;
    }
}

bool Pass(Maze maze, Pos pos)
{
    return maze[pos.x][pos.y] == 0;
}

void FootMaze(Maze maze,Pos pos)
{
    maze[pos.x][pos.y] = 2;
}

Pos NextPos(Pos pos, DIR di)
{
    switch(di)
    {
    case RIGHT:
        pos.y += 1;
        break;
    case DOWN:
        pos.x += 1;
        break;
    case LEFT:
        pos.y -= 1;
        break;
    case UP:
        pos.x -= 1;
        break;
    }
    return pos;
}

void MarkMaze(Maze maze, Pos pos)
{
    maze[pos.x][pos.y] = 4;
}

bool PassMaze(Maze maze,Pos start, Pos end)
{
    Man man; //pos di
    Stack<Man> st;
    Pos curpos = start;
    do
    {
        if(Pass(maze,curpos))
        {
            man.pos = curpos;
            man.di = RIGHT;
            FootMaze(maze,man.pos);
            if(curpos == end)
                return true;
            st.push(man);
            curpos = NextPos(man.pos,man.di);
        }
        else
        {
            if(!st.isempty())
            {
                man = st.gettop();
                while(man.di==UP && !st.isempty())
                {
                    st.pop();
                    MarkMaze(maze,man.pos);
                    if(!st.isempty())
                    {
                        man = st.gettop();
                    }
                    else
                    {
                        return false;
                    }

                }
                if(man.di < UP)
                {
                    st.pop();
                    man.di = (DIR)(man.di+1);
                    st.push(man);
                    curpos = NextPos(man.pos,man.di);
                }
            }
        }
    }while(!st.isempty());
    return false;
}

void main()
{
    Pos start = {0,1};
    Pos end = {9,8};
    Maze maze =
    {
        {1,0,1,1,1,1,1,1,1,1},
        {1,0,0,0,0,0,0,0,0,1},
        {1,0,1,1,1,1,1,1,1,1},
        {1,0,0,1,0,0,0,0,0,1},
        {1,0,1,1,1,1,1,1,0,1},
        {1,0,1,0,0,0,0,0,0,1},
        {1,0,0,0,0,1,0,1,1,1},
        {1,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,1,1,1,1,0,1},
        {1,1,1,0,0,0,0,0,0,1}
    };
    ShowMaze(maze);
    if(!PassMaze(maze,start,end))
    {
        cout<<"没有出路！"<<endl;
        return;
    }
    cout<<"-------------------"<<endl;
    ShowMaze(maze);

}