迷宫寻址代码分析

谁借莪１个温暖的怀抱￠ 2022-07-15 02:54 133阅读 0赞

最近学了堆栈，里面有个迷宫寻址的程序蛮有意思的，觉得程序的思路也很厉害。
    以下代码的迷宫寻址函数是《数据结构、算法与应用 C++语言描述》上的，自己也有一点小的改动。其中关于代码的分析都在注释中了，希望能看懂。

#include<iostream>
    using namespace std;
    struct Position
    {
        friend ostream& operator<<(ostream& out, Position& x);
        int row, col;
    };
    ostream& operator<<(ostream& out, Position& x)
    {
        cout << x.row << "," << x.col;
        return out;
    }
    template<typename T>
    class Stack
    {
    public:
        Stack(int size);
        ~Stack() { delete[] stack; }
        int Size()const { return top + 1; }
        bool IsEmpty() { return top == -1; }
        bool IsFull() { return top == size - 1; }
        void Add(const T& x);//往stack栈顶添加元素
        void Delete(T& x);//删除stack栈顶，并将删除的元素给x
        void Output()const;//输出stack中的所有元素
    private:
        T* stack;
        int size;
        int top;
    };
    template<typename T>
    Stack<T>::Stack(int size)
    {
        this->size = size;
        stack = new T[size];
        top = -1;
    }
    template<typename T>
    void Stack<T>::Add(const T& x)
    {
        if (IsFull())
            throw "THIS STACK IS FULL";
        stack[++top] = x;
    }
    template<typename T>
    void Stack<T>::Delete(T& x)
    {
        if (IsEmpty())
            throw "THIS STACK IS EMPTY";
        x = stack[top--];
    }
    
    template<typename T>
    void Stack<T>::Output()const
    {
        for (int i = 0; i <=top; i++)
            cout << stack[i]<<endl;
    }
    
    static Stack<Position>* path;   //用来存放路径
    //迷宫寻址函数
    bool FindPath(int m,int n,int** maze)
    {
        //寻找从位置(1,1)到出口(n,n)的路径
        //成功返回true，失败返回false
    
        path = new Stack<Position>(m*n-1);
        //对偏移量进行初始化
        Position offset[4];
        offset[0].row = 0; offset[0].col = 1;//往右走
        offset[1].row = 1; offset[1].col = 0;//往下走
        offset[2].row = 0; offset[2].col = -1;//往左走
        offset[3].row = -1; offset[3].col = 0;//往上走
        //在迷宫周围增加一圈障碍物:1表示能走，0表示不能走
        for (int i = 0; i <= m + 1; i++)maze[0][i] = maze[m+1][i] = 0;//顶部和底部
        for (int i = 0; i <= n + 1; i++)maze[i][0] = maze[i][n+1] = 0;//左部和右部
        //输出迷宫
        /*
        for (int i = 0; i <= m + 1; i++)
        {
            for (int j = 0; j <= n + 1; j++)
                cout << maze[i][j] << " ";
            cout << endl;
        }
        */
        Position here;
        here.row = here.col = 1;
        maze[1][1] = 0;//设为0防止到时候回到起点
        int option = 0;//选择走的方向:0往右走 1往下走 2往左走 3往上走
        int maxOption=3;//能选择的最大option
        while (!(here.row == m && here.col == n))//还没走到终点的时候继续寻址
        {
            //寻找并移动到一个相邻的位置
            int row, col;
            while (option <= maxOption)
            {
                row = here.row + offset[option].row;
                col = here.col + offset[option].col;
                if (maze[row][col])break;//某个方向能走时退出循环尝试寻址
                option++;
            }
            //找到能走的相邻位置
            if (option <= maxOption)
            {
                //这里的策略是将here作为一个候选者，先不将here放到path中去，如果here周围有能走的Position，将那个Position作为新的here，而原先的here放到path中去
                path->Add(here);
                here.row = row;
                here.col = col;
                //设置障碍继续寻址，防止新的here在寻址时将之前的here作为可走的路
                maze[row][col] = 0;
                option = 0;//开始在新的here附近找能走的路
            }
            //没有找到能走的相邻位置
            else
            {
                if (path->IsEmpty())return false;//没有找到相邻的能走的路，同时也没有退路，就返回false
                Position prePosition;//找不到能走的路就说明path栈顶的那个Position也是不能走的，所以要将原先的那个Position弹出栈
                path->Delete(prePosition);
                /*
                下面两行代码是关键，需要好好分析一下：
                因为是找path，所以path中任意两个相邻元素在迷宫maze中的位置一定也是相邻的，而path栈顶那个prePosition也一定和候选者here是相邻的
                先判断之前那个Position是不是和找不到可走路的here在同一行，
                如果在同一行，
                    （1）prePosition.col-here.col==1,即here在prePosition左侧，说明之前已经尝试过prePosition的右侧、下侧和左侧（根据之前的0右1下2左3上原则），那么接下来尝试走上侧的路；
                    （2）prePosition.col-here.col==-11,即here在prePosition右侧，说明之前只尝试过prePosition的右侧，那么接下来尝试走下侧的路；
                如果不在同一行（那么一定在同一列），分析过程同上。 注意如果这时option变成4后，说明prePosition也是一个四周都走不通的Position，那么还得退回到prePosition的prePosition，这类似于递归又回退，但又不是递归。因此如果此时option变成4后下一次直接跳到else中进行重新寻址
                */
                if (prePosition.row == here.row)option = 2 + prePosition.col - here.col;
                else option = 3 + prePosition.row - here.row;
                //这时候选的变成prePosition
                here = prePosition;
            }
        }
        return true;
    }
    int main()
    {
        int m,n;
        int** maze;
        //输入迷宫行数列数
        cin >> m >> n;
        //生成迷宫,加上周围的“围墙”
        maze = new int*[m + 2];
        for (int i = 0; i < m+2; i++)maze[i] = new int[n + 2];
        //输入迷宫
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                cin >> maze[i][j];
        if (FindPath(m, n, maze))
            path->Output();
        else
            cout << "Can not find the way " << endl;
    
    
        system("pause");
    }

下面是我的测试迷宫![这里写图片描述][20161030231346325]

[20161030231346325]: /images/20220715/2ec85d49c8ac460698a31de8a4708211.png