走迷宫

傷城~ 2022-06-17 07:12 213阅读 0赞

通过栈将每次可以通过的路径保存起来。  
但是要注意关于入口点和出口点的一些边界问题  
一不小心就可能因为边界问题陷入死循环或者程序直接崩溃。

#pragma warning (disable:4996)
    #include<iostream>
    #include<stdlib.h>
    #include<fstream> 
    #include<assert.h>
    #include<stack>
    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(int x = 0, int y = 0)
            :_row(x)
            , _col(y)
            , _map(NULL)
            , _start(0, 0)
        {
    
        }
        ~Maze()
        {
            if (_map != NULL)
            {
                for (int i = 0; i < _row; i++)
                {
                    delete[] _map[i];
                }
                delete[]  _map;
    
            }
        }
        void SetMap();
        void ShowMap();
        bool PassMaze();
        bool IsPass(Pos s);
        int _row;
        int _col;
        int **_map;
        Pos  _start;
        int size;
    };
    void Maze::SetMap()
    {
        char c;
        FILE *fp = fopen("maze.txt", "r");      //打开文件读取地图 
        assert(fp);
        //读取行 
        while ((c = fgetc(fp)) != ' '&&c != '\n')
        {
            _row = _row * 10 + (c - '0');
        }
        //读取迷宫列 
        while ((c = fgetc(fp)) != ' '&&c != '\n')
        {
            _col = _col * 10 + (c - '0');
        }
        //读取迷宫入口横坐标 
        while ((c = getc(fp)) != ' '&&c != '\n')
        {
            _start._Row = _start._Row * 10 + (c - '0');
        }
        //读取迷宫入口纵坐标 
        while ((c = getc(fp)) != ' '&&c != '\n')
        {
            _start._Col = _start._Col * 10 + (c - '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;)
            {
                c = getc(fp);  //开始按字符读取存入到_map的二维数组中
                if (c == '1' || c == '0')
                {
                    _map[i][j] = c - '0';
                    j++;
                }
            }
        }
        fclose(fp);     //关闭文件 
    }
    void Maze::ShowMap()
    {
        for (int i = 0; i < _row; i++)
        {
            for (int j = 0; j < _col; j++)
            {
                printf("%d ", _map[i][j]);
            }
            cout << endl;
        }
    }
    bool Maze::IsPass(Pos s)
    {
        if (s._Row>=0&&s._Row<_row&&s._Col>=0&&s._Col<_col&&_map[s._Row][s._Col] == 0)
        {
            return true;
        }
        else if (s._Row < 0 || s._Row >= _row || s._Col < 0 || s._Col >= _col)
        {
            return true;
        }//是为了判断已经越界则可以直接返回说明找到了出口
        else
        {
            return false;
        }
    }
    bool Maze::PassMaze()
    {
        stack<Pos> s;
        s.push(_start);
        Pos seat;
        Pos Cur;
        while (!s.empty())
        {
            seat = s.top();
            Cur = seat;
            if (Cur._Row < 0 || Cur._Row >= _row || Cur._Col < 0 || Cur._Col >= _col)
            {
                return true;
            }
            _map[Cur._Row][Cur._Col] = 2;
            Cur._Row--;
            //向前走
            if (IsPass(Cur))
            {
                s.push(Cur);
                continue;
            }
            Cur = seat;
            Cur._Col--;//向左走
              if (IsPass(Cur))
                {
                    s.push(Cur);
                    continue;
                }
            Cur = seat;
            Cur._Col++;//向右走
                if (IsPass(Cur))
                {
                    s.push(Cur);
                    continue;
                }
            Cur = seat;
            Cur._Row++;//向后走
                if (IsPass(Cur))
                {
                    s.push(Cur);
                    continue;
                }
                Cur = seat;
                s.pop();
                _map[Cur._Row][Cur._Col] = 3;
    
        }
        return false;
    
        return false;
    }
    void FunTest()
    {
        Maze p;
        p.SetMap();
        p.ShowMap();
        cout << endl;
        p.PassMaze();
        p.ShowMap();
        //p.PrintPath();
    }
    int main()
    {
        FunTest();
        /*p.ShowMap();*/
        system("pause");
        return 0;
    }