[数据结构与算法]迷宫问题-深度搜索-数据结构-栈应用

#include<iostream>
#include<stack>

using namespace std;
struct index
{
    int x;
    int y;
    index(int x, int y) :x(x), y(y) {}
};


class S :public stack<index>
{

public:
    int lx, ly, ox, oy, w, h;
    int **maze;
    bool **mark;
    S(int** p, int w, int h) :stack<index>()
    {
        maze = p;
        this->w = w;
        this->h = h;
        mark = new bool*[h];
        for (int i = 0; i < h; i++)
        {
            mark[i] = new bool[w];
            for (int j = 0; j < w; j++)
                mark[i][j] = false;
        }
    }
    void get_last()
    {
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (maze[i][j] == 4)
                {
                    this->lx = i;
                    this->ly = j;
                    return;
                }
            }
        }
    }
    void get_orginal()
    {
        for (int i = 0; i < h; i++)
        {

            for (int j = 0; j < w; j++)
            {

                if (maze[i][j] == 3)
                {
                    this->ox = i;
                    this->oy = j;
                    return;
                }
            }

        }
    }
    bool seekpath(int x, int y)
    {
        index ind(x, y);
        mark[x][y] = true;

        push(ind);
        if (maze[x][y] == 4)
        {
            cout << *this;
            return 1;
        }
        if ((x + 1) < h && !this->panduan(x + 1, y) && maze[x + 1][y] != 1 && maze[x + 1][y] != 3 && seekpath(x + 1, y)) { return 1; }
        if ((y - 1) >= 0 && !this->panduan(x, y - 1) && maze[x][y - 1] != 1 && maze[x][y - 1] != 3 && seekpath(x, y - 1)) { return 1; }
        if ((x - 1) >= 0 && !this->panduan(x - 1, y) && maze[x - 1][y] != 1 && maze[x - 1][y] != 3 && seekpath(x - 1, y)) { return 1; }
        if ((y + 1) < w && !this->panduan(x, y + 1) && maze[x][y + 1] != 1 && maze[x][y + 1] != 3 && seekpath(x, y + 1)) { return 1; }
        pop();
        return 0;
    }
    friend ostream& operator<<(ostream& out, S& s) {
        stack<index> s1;
        while (!s.empty()) {

            s1.push(s.top());
            s.pop();
        }
        while (!s1.empty())
        {
            index indx = s1.top();
            out << indx.y << " " << indx.x << endl;
            s1.pop();
        }
        return out;
    }
    bool panduan(int x,int y) {
        return mark[x][y];

    }

};

int main()
{

    int w, h;
    cin >> w >> h;

    int** maze;
    maze = new int*[h];
        for (int i = 0; i < h; i++)
        {
            maze[i] = new int[w];
        }
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> maze[i][j];
        }
    }
    S s(maze, w, h);
    s.get_orginal();
    s.seekpath(s.ox, s.oy);
    for(int i =0;i<h;i++)
    {
        delete[] maze[i];
    
    }
    delete[] maze;
    return 0;
}