走迷宫问题

朱雀 2022-05-31 05:30 277阅读 0赞

## 问题描述： ##

给一迷宫表个和入口位置，找出并打印出从入口到出口的路径

注意：迷宫表格我们可以用一个二维数组来表示，但是如果用二维数组表示，将唯一固定，迷宫趣味性大大降低并代码长度增大；因此，我们最好是将迷宫表格存储在一文件中，在实现时再从文件中读取；

采用模板来实现可实现复用性；

## 设计分析： ##

1、我们可沿着入口逐一方向进行试探，若有通则继续前进，全不通，回溯法则回溯，递归法则到达递归终止条件。

2、采用栈来记录走过的路径

### 迷宫表我放在：maze.txt文件中 ###

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

### 1、回溯法实现代码： ###

maze.h

#pragma once
    
    #include <iostream>
    using namespace std;
    #include <assert.h>
    #include <stack>
    
    struct Pos   //放置位置
    {
        Pos(const size_t& row, const size_t& col)
            :_row(row)
            , _col(col)
        {}
        int _row;
        int _col;
    };
    
    template <size_t M, size_t N>
    class maze
    {
    public:
        maze()   
        {
            FILE * fr = fopen("maze.txt", "r");
            assert(fr);
            for (size_t i = 0; i < M; ++i)
            {
                for (size_t j = 0; j < N; )
                {
                        char ch = fgetc(fr);
                        if ((ch=='1') || (ch == '0'))    //迷宫表之间存在空格，不是我们要的数据
                        {
                            _array[i][j] = ch - '0';
                            ++j;
                        }
                }
            }
        }
        void Print()   //打印迷宫表
        {
            for (size_t i = 0; i < M; ++i)
            {
                for (size_t j = 0; j < N;++j)
                {
                    cout << _array[i][j]<<" ";
                }
                cout << endl;
            }
            cout << endl;
        }
    
        bool CheckPass(Pos& next)   //1、判断是否为通2、判断位置是否合法
        {
            if ((next._row >= 0) && (next._row < M) && (next._col >= 0) && (next._col < N) &&
                (_array[next._row][next._col]==0))
            {
                return true;
            }
            return false;
        }
    
        bool GetMazePath(Pos entry)  //走迷宫
        {
            stack<Pos> path;
            path.push(entry); //入口进栈
            _array[entry._row][entry._col] = 2;
    
            while (!path.empty())   //栈非空
            {
                Pos cur = path.top();
                Pos next = cur;
                //探测右
                next = cur;
                next._col += 1;
                if (CheckPass(next))
                {
                    path.push(next);
                    _array[next._row][next._col] = 2;
                    continue;
                }
                //探测上
                next._row -= 1;
                if (CheckPass(next))
                {
                    path.push(next);
                    _array[next._row][next._col] = 2;
                    continue;
                }
                //探测下
                next = cur;
                next._row += 1;
                if (CheckPass(next))
                {
                    path.push(next);
                    _array[next._row][next._col] = 2;
                    continue;
                }
                //探测左
                next = cur;
                next._col -= 1;
                if (CheckPass(next))
                {
                    path.push(next);
                    _array[next._row][next._col] = 2;
                    continue;
                }
    
                if (next._row == M - 1)
                {
                    cout << "出来了" << endl;
                    return true;
                }
                //均不符合
                Pos pos = path.top();
                _array[pos._row][pos._col] = 3;
                path.pop();
    
            }
            return false;
        }
    private:
        size_t _array[M][N];
    };

### 测试代码：test.c ###

#include <iostream>
    #include "maze.h"
    using namespace std;
    int main()
    {
        Pos entry = { 3, 0 };
        maze<10, 10> a;
        a.Print();
        a.GetMazePath(entry);
    
        a.Print();
        system("pause");
        return 0;
    }

### 2、递归法代码： ###

maze.h

#pragma once
    
    #include <iostream>
    using namespace std;
    #include <assert.h>
    #include <stack>
    
    struct Pos   //放置位置
    {
        Pos(const size_t& row, const size_t& col)
            :_row(row)
            , _col(col)
        {}
        int _row;
        int _col;
    };
    
    template <size_t M, size_t N>
    class maze
    {
    public:
        maze()   
        {
            FILE * fr = fopen("maze.txt", "r");
            assert(fr);
            for (size_t i = 0; i < M; ++i)
            {
                for (size_t j = 0; j < N; )
                {
                        char ch = fgetc(fr);
                        if ((ch=='1') || (ch == '0'))    //迷宫表之间存在空格，不是我们要的数据
                        {
                            _array[i][j] = ch - '0';
                            ++j;
                        }
                }
            }
        }
        void Print()   //打印迷宫表
        {
            for (size_t i = 0; i < M; ++i)
            {
                for (size_t j = 0; j < N;++j)
                {
                    cout << _array[i][j]<<" ";
                }
                cout << endl;
            }
            cout << endl;
        }
    
        bool CheckPass(Pos& next)   //1、判断是否为通2、判断位置是否合法
        {
            if ((next._row >= 0) && (next._row < M) && (next._col >= 0) && (next._col < N) &&
                (_array[next._row][next._col]==0))
            {
                return true;
            }
            return false;
        }
    
    
        bool GetMazePathR(Pos cur)  //走迷宫
        {
            if (cur._row == M-1)
            {
                return true;
            }
    
            Pos next = cur;
            _array[next._row][next._col] = 2;
    
            //探测右
            next._col += 1;
            if (CheckPass(next))
            {
                _array[next._row][next._col] = 2;
                if (GetMazePathR(next))     
                {
                    return true;
                }
            }
            //探测上
            next = cur;
            next._row -= 1;
            if (CheckPass(next))
            {
                _array[next._row][next._col] = 2;
    
                if (GetMazePathR(next))
                {
                    return true;
                }
            }
            //探测下
            next = cur;
            next._row += 1;
            if (CheckPass(next))
            {
                _array[next._row][next._col] = 2;
    
                if (GetMazePathR(next))
                {
                    return true;
                }
            }
            //探测左
            next = cur;
            next._col -= 1;
            if (CheckPass(next))
            {
                _array[next._row][next._col] = 2;
    
                if (GetMazePathR(next))
                {
                    return true;
                }
            }
            return false;
        }
    
    private:
        size_t _array[M][N];
    };

### 测试代码：test.c ###

### 两个结果是相同的，均可找到迷宫的路径 ###

结果截图：

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

[SouthEast]: /images/20220531/6f14bd4e4c284b8da2c92f79fe1764fd.png
[SouthEast 1]: /images/20220531/96957291c3cc434f91039e7fbd7d7628.png