递归和栈求解迷宫的最短路径

ゝ一纸荒年。 2022-06-15 23:42 302阅读 0赞

采用递归的方式求最短路径  
1、用一个栈专门用来保存有效的路径  
2、再用一个栈来辅助保存所有走过的路径。  
3、然后再用一个栈用来保存最短的路径  
4、如果每次找到了出口，那么必然有两个栈一个保存了所有走过的路径，一个保存了通路的路径  
5、于是每找到一次出口，那么开始进行比较，如果当前最短路径中所保存的每个坐标的个数如果大于本次通路的路径，那么就将最短路径中的所有数据出栈，并将本次通路的路径放入最短路径的栈中，然后开始把本次路径的出口堵死，将其他走过的路径全部初始化为原始状态（也就是将所有走过的所有路径再次全部标记成可以走的）  
6、然后继续递归调用找路径的这个函数，直到所有路径都找完了，仍旧没有出路。就开始一层一层的往回返。

#include<iostream>
    #include<stdlib.h>
    #include<assert.h>
    #include<stack>
    #pragma warning(disable:4996)
    using namespace std;
    class Pos
    {
    public:
        Pos(int x=0, int y=0)
            :_row(x)
            ,_col(y)
        {
    
        }
        int _row;
        int _col;
    };
    class Maze
    {
    public: 
        Maze();
        ~Maze();
        void InitMap();
        bool  CheckIsPath(Pos seat);
        bool GetMazePath();
        void  PrintMap();
        int _row;
        int _col;
        int **_map;//存放迷宫的地图，使用二级指针来保存二维数组
        Pos _entry;
        Pos **_path;
        stack<Pos>_shortpath;
        int row;
        int col;
    };
    Maze::Maze()
        :_row(0)
        , _col(0)
        , _map(NULL)
        , _entry(0,0)
    {
    
    }
    Maze::~Maze()
    {
        if (_map)
        {
            for (int i = 0; i < _row; i++)
            {
                delete[] _map[i];
            }
            delete _map;
            _map = NULL;
        }
    }
    
    void Maze::InitMap()
    {
        char ch;
        FILE* fp = fopen("maze.txt", "r");
        assert(fp);
        while ((ch = fgetc(fp)) != ' '&&ch != '\n')
        {
            _row = _row * 10 + ch - '0';
        }
        while ((ch = fgetc(fp)) != ' '&&ch != '\n')
        {
            _col = _col * 10 + ch - '0';
        }
        while ((ch = fgetc(fp)) != ' '&&ch != '\n')
        {
            _entry._row = _entry._row * 10 + ch - '0';
        }
        while ((ch = fgetc(fp)) != ' '&&ch != '\n')
        {
            _entry._col = _entry._col * 10 + ch - '0';
        }
    
        _map = new int*[_row];
        for (int i = 0; i < _row; i++)
        {
            _map[i] = new int[_col];
        }//动态的开辟二维数组的空间
    
        for (int i = 0; i < _row; i++)
        {
            for (int j = 0; j < _col;)
            {
                ch = fgetc(fp);
                if (ch == '0' || ch == '1')
                {
                    _map[i][j] = ch - '0';
                    ++j;
                }
            }
        }
        fclose(fp);
    }
    bool  Maze::CheckIsPath(Pos s)
    {
        if (s._row >= 0 && s._row < _row && s._col >= 0&& s._col < _col && _map[s._row][s._col]==0)
        {
            return true;
        }
        return false;
    }
    bool  Maze::GetMazePath()
    {
        stack<Pos> s;
        stack<Pos>s1;//辅助保存所有走过的路径
        s.push(_entry);
        s1.push(_entry);
        while (!s.empty())
        {
            Pos cur = s.top();
            _map[cur._row][cur._col] = 2;
            Pos next = cur;
            if ((next._row == 0 || next._row == _row-1  || next._col == 0 || next._col == _col-1)&&next._row!=_entry._row&&next._col!=_entry._col)
            {
    
               if (_shortpath.size() > s.size()||_shortpath.size()==0)//如果最短路径的栈中元素个数为0或者他的大小大于本次通路路径的个数那么就更新最短路径
                {
                    while (!_shortpath.empty())
                    {
                        Pos temp = _shortpath.top();
                        _shortpath.pop();
                    }
                    while (!s.empty())//更新完成之后将保存本次通路路径的栈的所有元素出栈，以便于保存下次通路的路径
                    {
    
                        Pos temp = s.top();
                        _shortpath.push(temp);
                        s.pop();
                    }
                }
                else//如果当前的路径本就是最短路径，那么删除保存的当前通路的路径，将所有走过的
                {
                    while (!s.empty())
                    {
                        Pos temp = s.top();
                        s.pop();
                    }
                }
               while (!s1.empty())//将所有走过的路径全部初始化程原来通路的状态
               {
                   Pos temp = s1.top();
                   _map[temp._row][temp._col] = 0;
                   s1.pop();
               }
                _map[next._row][next._col] = 4;//将本次通路的出口都死，以便于寻找下一条合适的路径
                PrintMap();
                cout << endl;
                GetMazePath();//递归调用，继续寻找下一条路径
                return true;
            }
            next = cur;
            next._row = next._row-1;
            if (CheckIsPath(next))
            {
                s.push(next);
                s1.push(next);
                continue;
            }
            next=cur;//下
            next._row = next._row + 1;
            if (CheckIsPath(next))
            {
                s.push(next);
                s1.push(next);
                continue;
            }
            next = cur;
            next._col = next._col - 1;//左
            if (CheckIsPath(next))
            {
                s.push(next);
                s1.push(next);
                continue;
            }
            next = cur;
            next._col = next._col + 1;//右
            if (CheckIsPath(next))
            {
                s.push(next);
                s1.push(next);
                continue;
            }   
                _map[cur._row][cur._col] = 3;
                s1.push(cur);
                s.pop();
        }
        return false;
    }
    void  Maze::PrintMap()
    {
        for (int i = 0; i < _row; i++)
        {
            for (int j = 0; j < _col; j++)
            {
                cout << _map[i][j] << " ";
            }
            cout << endl;
        }
    }
    void FunTest()
    {
        Maze a;
        a.InitMap();
        a.PrintMap();
        cout << endl;
        a.GetMazePath();
        cout << endl;
        a.PrintMap();
        //cout << a._shortpath.size()<<endl;
        for (int i = 0; i < (a._shortpath).size();)
        {
            Pos temp = (a._shortpath).top();
            cout << temp._row << "," << temp._col << endl;
            (a._shortpath).pop();
        }
    }
    int main()
    { 
        FunTest();
        system("pause");
        return 0;
    }

但是这样求解迷宫最短路径是有问题的，因为有可能我不同的路径是同一个出口，这样直接把出口堵死，很有可能就找不到出口是同一个路径了。  
为了解决迷宫最短路径不能采用以上的方式。只能采用递归的方式将每一条路径都遍历一遍，但同时改变之前所使用的标记方式，因为如果还按照之前的标记方式，就会因为走过而不会再走，导致求解最短路径出错。

bool  Maze::GetMazePath(Pos cur,stack<Pos>&path)
    {
        //cur = _entry;
        Pos next = cur;
        path.push(cur);
        _map[cur._row][cur._col] = 2;
        if (cur._row == _row - 1 || cur._row == 0 || cur._col == _col - 1 || cur._col == 0)
        {
            return true;
        }
        next = cur;
        next._row -= 1;//往上走
        if (CheckIsPath(next))
        {
            GetMazePath(next, path);
            return true;
        }
        next = cur;
        next._row += 1;//往下走
        if (CheckIsPath(next))
        {
            GetMazePath(next, path);
            return true;
        }
        next = cur;
        next._col -= 1;//往左走
        if (CheckIsPath(next))
        {
            GetMazePath(next, path);
            return true;
        }
        next = cur;
        next._col+= 1;//往右走
        if (CheckIsPath(next))
        {
            GetMazePath(next, path);
            return true;
        }
        _map[cur._row][cur._col] = 3;
        return false;
    }
    void  Maze::PrintMap()
    {
        for (int i = 0; i < _row; i++)
        {
            for (int j = 0; j < _col; j++)
            {
                cout << _map[i][j] << " ";
            }
            cout << endl;
        }
    }

改变代码

bool  Maze::GetMazePath(Pos cur,stack<Pos>&path,stack<Pos>&shortpath)
    {
        //cur = _entry;
        Pos next = cur;
        path.push(cur);
        _map[cur._row][cur._col] = 2;
        if (cur._row == _row - 1 || cur._row == 0 || cur._col == _col - 1 || cur._col == 0)
        {
            if (shortpath.size() == 0 || shortpath.size() > path.size())
            {
                shortpath = path;
            }
            return true;
        }
        next = cur;
        next._row -= 1;//往上走
        if (CheckIsPath(next))
        {
            GetMazePath(next, path,shortpath);
        }
        next = cur;
        next._row += 1;//往下走
        if (CheckIsPath(next))
        {
            GetMazePath(next, path, shortpath);
        }
        next = cur;
        next._col -= 1;//往左走
        if (CheckIsPath(next))
        {
            GetMazePath(next, path, shortpath);
        }
        next = cur;
        next._col+= 1;//往右走
        if (CheckIsPath(next))
        {
            GetMazePath(next, path, shortpath);
        }
        _map[cur._row][cur._col] = 3;
        path.pop();
    }

即使这样，但是求解迷宫最短路径还是存在问题  
为了解决这个问题，很明显我们需要解决标记带来的问题。  
此时不再使用简单的方式来标记走过的路径。

bool  Maze::CheckIsPath(Pos cur,Pos next)
    {
        if (next._row >= 0 && next._row < _row && next._col >= 0 && next._col < _col)
        {
            if (_map[next._row][next._col] == 0 || _map[next._row][next._col]>_map[cur._row][cur._col])
            {
                return true;
            }
        }
        return false;
    }
    bool  Maze::GetMazePath(Pos cur,stack<Pos>&path,stack<Pos>&shortpath)
    {
        //cur = _entry;
        Pos next = cur;
        path.push(cur);
        if (cur._row == _row - 1 || cur._row == 0 || cur._col == _col - 1 || cur._col == 0)
        {
            if (shortpath.size() == 0 || shortpath.size() > path.size())
            {
                shortpath = path;
            }
            return true;
        }
        next = cur;
        next._row -= 1;//往上走
        if (CheckIsPath(cur,next))
        {
            _map[next._row][next._col] = _map[cur._row][cur._col] + 1;
            GetMazePath(next, path, shortpath);
        }
        next = cur;
        next._row += 1;//往下走
        if (CheckIsPath(cur, next))
        {
            _map[next._row][next._col] = _map[cur._row][cur._col] + 1;
            GetMazePath(next, path, shortpath);
        }
        next = cur;
        next._col -= 1;//往左走
        if (CheckIsPath(cur, next))
        {
            _map[next._row][next._col] = _map[cur._row][cur._col] + 1;
            GetMazePath(next, path, shortpath);
        }
        next = cur;
        next._col+= 1;//往右走
        if (CheckIsPath(cur, next))
        {
            _map[next._row][next._col]=_map[cur._row][cur._col] + 1;
            GetMazePath(next, path, shortpath);
    
        }
        path.pop();
    }
    void  Maze::PrintMap()
    {
        for (int i = 0; i < _row; i++)
        {
            for (int j = 0; j < _col; j++)
            {
                cout << _map[i][j] << " ";
            }
            cout << endl;
        }
    }

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

[SouthEast]: /images/20220616/a384d36052dd4a758a83e4aefe282d5b.png