c++ stack迷宫求解

根提供的引用内容，程序中定义了一个名为boos的类，其中包括了栈的基本方法和走迷宫的方法。栈的基本方法包括InitStack（创建栈）、StackEmpty（判断是否空栈）、GetTop（获得栈顶）、Push（入栈）、Pop（出栈）以及free_Stack（释放栈空间）。走迷宫的方法是利用顺序栈求解迷宫中从入口到出口的一条路径，并输出结果。

迷宫的表示使用了一个二维数组maze，其中1表示路不通，0表示可以通过。具体的迷宫规模和初态可以自行定义。通过调用boos类的findMaze方法，可以找到迷宫中从入口到出口的一条路径。

以下是一个示例的C++代码，演示了如何利用栈求解迷宫问题：

#include <iostream>
#include <cstdlib>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct {
    int x; // 坐标
    int y; // 坐标
    int di; // 方向
} position;

typedef struct {
    position *base;
    position *top;
    int stacksize;
} Stack;

class boos {
private:
    Stack sq_stack;

public:
    void InitStack() {
        // 创建栈
        sq_stack.base = new position[STACK_INIT_SIZE];
        sq_stack.top = sq_stack.base;
        sq_stack.stacksize = STACK_INIT_SIZE;
    }

    bool StackEmpty() {
        // 判断是否空栈
        return sq_stack.top == sq_stack.base;
    }

    bool GetTop(position &temp) {
        // 获得栈顶
        if (sq_stack.top == sq_stack.base) {
            return false;
        }
        temp = *(sq_stack.top - 1);
        return true;
    }

    bool Push(position &temp) {
        // 入栈
        if (sq_stack.top - sq_stack.base >= sq_stack.stacksize) {
            sq_stack.base = (position *)realloc(sq_stack.base, (sq_stack.stacksize + STACKINCREMENT) * sizeof(position));
            if (!sq_stack.base) {
                return false;
            }
            sq_stack.top = sq_stack.base + sq_stack.stacksize;
            sq_stack.stacksize += STACKINCREMENT;
        }
        *sq_stack.top++ = temp;
        return true;
    }

    bool Pop(position &temp) {
        // 出栈
        if (sq_stack.top == sq_stack.base) {
            return false;
        }
        temp = *--sq_stack.top;
        return true;
    }

    void free_Stack() {
        // 释放栈空间
        delete[] sq_stack.base;
    }

    bool findMaze(int start_x, int start_y, int end_x, int end_y) {
        // 迷宫的入口和出口坐标
        position curpos;
        curpos.x = start_x;
        curpos.y = start_y;
        curpos.di = -1;
        Push(curpos);

        while (!StackEmpty()) {
            GetTop(curpos);
            if (curpos.x == end_x && curpos.y == end_y) {
                while (!StackEmpty()) {
                    Pop(curpos);
                    std::cout << "(" << curpos.x << "," << curpos.y << ") ";
                }
                return true;
            }

            int i = curpos.x;
            int j = curpos.y;
            int di = curpos.di + 1;

            while (di < 4) {
                switch (di) {
                    case 0: // 向右
                        i = curpos.x;
                        j = curpos.y + 1;
                        break;
                    case 1: // 向下
                        i = curpos.x + 1;
                        j = curpos.y;
                        break;
                    case 2: // 向左
                        i = curpos.x;
                        j = curpos.y - 1;
                        break;
                    case 3: // 向上
                        i = curpos.x - 1;
                        j = curpos.y;
                        break;
                }

                if (Maze[i][j] == 0) {
                    Maze[i][j] = -1;
                    position nextpos;
                    nextpos.x = i;
                    nextpos.y = j;
                    nextpos.di = 0;
                    Push(nextpos);
                    break;
                } else {
                    di++;
                }
            }

            if (di == 4) {
                Maze[curpos.x][curpos.y] = -1;
                Pop(curpos);
            }
        }

        return false;
    }
};

int main() {
    int start_x = 1;
    int start_y = 1;
    int end_x = 8;
    int end_y = 8;

    boos L1;
    L1.InitStack();
    L1.findMaze(start_x, start_y, end_x, end_y);
    L1.free_Stack();

    return 0;
}

以上代码实现了利用栈求解迷宫问题。在示例中，迷宫的入口坐标为(1, 1)，出口坐标为(8, 8)。程序通过调用boos类的findMaze方法，找到了从入口到出口的一条路径，并将路径输出到控制台。