数据结构-迷宫问题（回溯法）

Bertha 。 2022-06-04 09:42 380阅读 0赞

> #### **题目描述：** ####

##### 迷宫是一个二维矩阵,其中1为墙,0为路,入口在第一列,出口在最后一行。要求从入口开始,从出口结束,按照 上,下,左,右 的顺序来搜索路径.。 #####

> #### **思路：** ####

##### 回溯法 + 试探法。回溯法可用栈或递归，**每次将走过的坐标进行标记，**防止再次回头造成死循环。 #####

--------------------

> #### **准备工作：**位置信息 ####

struct Pos
    {
        int _row;
        int _col;
    
        Pos(const int& x, const int& y)
            :_row(x)
            ,_col(y)
        {}
    };
    
        //一、二、三通用
        bool CheckAccess(Pos pos)
        {
            //1、边界条件
            //2、判断是否能通
            if ( (pos._row < N && pos._row >= 0 ) && ( pos._col < N && pos._col >= 0 )
                && _maze[pos._row][pos._col] == 0)
            {
                return true;
            }
            return false;
        }

--------------------

> #### **一、递归写法（同时创建一个栈保存了通路的坐标）** ####

##### 思路：首先需要将整个问题划分为子问题。如果子问题能通，那该问题也能通。转换为代码就是，先给定入口点，以该点为中心，分别试探上下左右四个放下，一旦某个方向能通，则递归为子问题，再以子问题为中心，分别探测；再回溯的时候，加入子问题四个位置都不能通，则函数栈帧销毁，自动回到该子问题的父问题。 #####

bool GetPathR(Pos entry, stack<Pos>& path)
        {
    
            path.push(entry);
            //标记该点，防止回头
            _maze[entry._row][entry._col] = 2;
    
            if (entry._row == N - 1)
                return true;
    
            //分别探测上,下，左右
            Pos next = entry;
            next._row -= 1;
            if (CheckAccess(next))
            {
                if (GetPathR(next, path))
                    return true;
            }
    
            next = entry;
            next._row += 1;
            if (CheckAccess(next))
            {
                if (GetPathR(next, path))
                    return true;
            }
    
            next = entry;
            next._col -= 1;
            if (CheckAccess(next))
            {
                if (GetPathR(next, path))
                    return true;
            }
    
            next = entry;
            next._col += 1;
            if (CheckAccess(next))
            {
                if (GetPathR(next, path))
                    return true;
            }
    
            //该位置走不通
            path.pop();
            return false;
        }

![这里写图片描述][SouthEast]

--------------------

> #### **二、用栈来改造递归的实现：** ####

bool GetPathWithStack(Pos entry,stack<Pos>& path)
        {
            path.push(entry);
            while (!path.empty())
            {
                Pos cur = path.top();
                //标记该位置
                _maze[cur._row][cur._col] = 2;
                if (cur._row == N - 1)
                    return true;
    
                //判断上
                Pos next = cur;
                next._row -= 1;
                if (CheckAccess(next))
                {
                    path.push(next);
                    continue;
                }
    
                //判断下
                next = cur;
                next._row += 1;
                if (CheckAccess(next))
                {
                    path.push(next);
                    continue;
                }
    
                //判断左
                next = cur;
                next._col -= 1;
                if (CheckAccess(next))
                {
                    path.push(next);
                    continue;
                }
    
                //判断右
                next = cur;
                next._col += 1;
                if (CheckAccess(next))
                {
                    path.push(next);
                    continue;
                }
    
                //上下左右都不可同，回溯pop掉该位置
                path.pop();
            }
            return false;
        }

--------------------

> #### **对于例一、二的测试：** ####

void Test1()
    {
        //0为可以走得路
        int mz[10][10] =
        {
            { 1,1,1,1,1,1,1,1,1,1 },
            { 1,1,1,1,1,1,1,1,1,1 },
            { 0,0,0,1,1,1,1,1,1,1 },
            { 1,1,0,1,1,1,1,1,1,1 },
            { 1,1,0,0,0,0,0,0,1,1 },
            { 1,1,1,1,1,0,1,0,1,1 },
            { 1,1,1,1,1,0,1,0,1,1 },
            { 1,1,1,1,1,0,1,0,1,1 },
            { 1,1,1,1,1,0,1,0,1,1 },
            { 1,1,1,1,1,1,1,0,1,1 }
        };
    
        //栈实现
        Maze<10> maze(mz);
        stack<Pos> path;
        //cout << maze.GetPathWithStack(Pos(2, 0), path) << endl;
        cout << maze.GetPathR(Pos(2, 0), path) << endl;
    
        maze.PrintMaze();
        maze.PrintPath(path);
    }

##### **输出截图（递归写法和用栈写法结果相同）：** #####

![这里写图片描述][SouthEast 1]

--------------------

> #### **三、多出口求出最短路径（改造上面代码）** ####

##### **思路：**多使用一个用来存最短路径的栈，当该条路径已经到出口的时候，path中存放了此路径上的坐标，与此同时和用来存放最短路径的shortPath的元素个数比，shortPath栈始终存放的是步数最短的路径。 #####

void GetShotPath(Pos entry, stack<Pos>& path, stack<Pos>& shortPath)
        {
            path.push(entry);
            _maze[entry._row][entry._col] = 2;
    
            if (entry._row == N - 1)
            {
                //判断size，若小于shortpath则该路径为新的最短路径
                if (path.size() < shortPath.size() || shortPath.empty())
                {
                    shortPath = path;
                    return;
                }
            }
    
            Pos next = entry;
            //探测上
            next._row -= 1;
            if (CheckAccess(next))
                GetShotPath(next,path,shortPath);
    
            //下
            next = entry;
            next._row += 1;
            if (CheckAccess(next))
                GetShotPath(next,path,shortPath);
    
            //左
            next = entry;
            next._col -= 1;
            if (CheckAccess(next))
                GetShotPath(next, path, shortPath);
    
            //右
            next = entry;
            next._col += 1;
            if (CheckAccess(next))
                GetShotPath(next, path, shortPath);
    
            path.pop();
        }
    
    //测试：
    void Test2()
    {
        int mz[10][10] =
        {
            { 1,1,1,1,1,1,1,1,1,1 },
            { 1,1,1,1,1,1,1,1,1,1 },
            { 0,0,0,0,0,0,1,1,1,1 },
            { 1,1,1,1,1,0,1,1,1,1 },
            { 1,1,0,0,0,0,0,0,1,1 },
            { 1,1,0,1,1,0,1,0,1,1 },
            { 1,1,0,1,1,0,1,0,1,1 },
            { 1,1,0,1,1,0,1,0,1,1 },
            { 1,1,0,1,1,0,1,0,1,1 },
            { 1,1,0,1,1,0,1,0,1,1 }
        };
    
        Maze<10> maze(mz);
        stack<Pos> path;
        stack<Pos> shortPath;
        maze.GetShotPath(Pos(2,0), path, shortPath);
        maze.PrintMaze();
        maze.PrintPath(shortPath);
    }

![这里写图片描述][SouthEast 2]

--------------------

> #### **四、带环迷宫** ####

##### 注：之前我们用的方法都是将走过的点标记为2，但是对于带环问题如果还是像之前一样，就会出现错误。比如像下面的图：本来应该是两条路径到出口点，但是如果按照之前的标记方式走的话，第二条路就会出现问题。下图中按照上下左右的探测方式来走：首先先完成第一幅图的内容；此时对\[9,5\]该进行回溯，一直回溯到\[4,5\]，递归走右，一直递归到\[2,3\]，到此图二走完；再对\[2,3\]进行回溯，一直回到\[2,2\]，本来最初\[2,2\]直接按照顺序向下探测进行递归，右侧还有一条属于自己的路，但是此时由于之前\[4,5\]的向右递归，影响了自己的路径。这时候如果两条路径长短不一致，恰好又要找到最短路径，那么就会出问题。 #####

![这里写图片描述][SouthEast 3]

--------------------

##### 通过上面的描述，显然之前的标记方法已经不使用于当前的情景，所以需要使用另外一种方法，不能造成因为是别人走过我的路，我就不能走我自己的路的惨剧。这种方法就是：一开始可以用2来标记，以便区别开0和1，之后每次都将子问题的值标记为当前位置的值加1，这样两条路就都会遍历到，从而找到最短路径。实现如下： #####

--------------------

void CricleMaze(Pos entry,stack<Pos>& path, stack<Pos>& shortPath,int count)
        {
            _maze[entry._row][entry._col] = ++count;
            path.push(entry);
            if (entry._row == N - 1)
            {
                printf("出口点为[%d,%d]\n", entry._row, entry._col);
                if (path.size() < shortPath.size() || shortPath.empty())
                {
                    shortPath = path;
                    return;
                }
            }
    
            Pos next = entry;
            //探测上
            next._row -= 1;
            if (CheckAccess(entry,next))
                CricleMaze(next,path,shortPath,count);
    
            //下
            next = entry;
            next._row += 1;
            if (CheckAccess(entry, next))
                CricleMaze(next, path, shortPath, count);
    
            //左
            next = entry;
            next._col -= 1;
            if (CheckAccess(entry, next))
                CricleMaze(next, path, shortPath, count);
            //右
            next = entry;
            next._col += 1;
            if (CheckAccess(entry, next))
                CricleMaze(next, path, shortPath, count);
    
            path.pop();
        }
    
    
    
        bool CheckAccess(Pos cur, Pos next)
        {
            //1.检查边界
            //2.是否是通路 0
            //3.比我大可以走，因为是别人走过的我没走过
            if ((next._row < N && next._row >= 0) && (next._col < N && next._col >= 0)
                && ( (_maze[next._row][next._col] == 0) || (_maze[cur._row][cur._col] < _maze[next._row][next._col])))
            {
                return true;
            }
            return false;
        }
    
    //测试
    void Test3()
    {
        Maze<10> maze(mz);
        stack<Pos> path;
        stack<Pos> shortPath;
    
        maze.CricleMaze(Pos(2, 0),path,shortPath,1);
        maze.PrintMaze();
        maze.PrintPath(shortPath);
    }

--------------------

##### 输出结果及分析： #####

![这里写图片描述][SouthEast 4]

--------------------

##### 由于给的图中，第二次遍历的路径走到\[4,7\]的时候，发现左侧要比自己要就停止了继续递归下去。这是由于我们的判断条件导致，只有当第二条路径比第一条短的时候才会接着递归，再更新最短路径。所以在遇到问题是，尽量采用最后一种标记方法来实现，以免出现带环路径， #####

![这里写图片描述][SouthEast 5]

--------------------

[SouthEast]: /images/20220604/8e24f3ad1d6a4052a84e808aa1590eba.png
[SouthEast 1]: /images/20220604/dac2ca5251ce4959a7f7b6f155a984d4.png
[SouthEast 2]: /images/20220604/bb4920f1adb14e55a62b61128afa9af5.png
[SouthEast 3]: /images/20220604/9eb5891bcbc742faa0c03ccc81bcff24.png
[SouthEast 4]: /images/20220604/d24143a8da7f46a48c50a2b58504e15f.png
[SouthEast 5]: /images/20220604/cb0a2e55f4c7436aad16071703bf4727.png