简单的迷宫问题(递归函数)（c++）

╰半橙微兮° 2023-10-06 17:14 29阅读 0赞

## 简单的迷宫问题(递归函数)（c++） ##

当初做这个题时，上网找了又找，大多数是用栈啊，链表啊，又臭又长。后来呢，稍微变通了一下，简便了一点。

题目如下：

迷宫是一个n\*m的矩阵，玩家需要迷宫入口（坐标1,1）出发，寻找路径走到出口（n,m）。

请判断玩家能否从迷宫中走出。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUxMjk3OTg3_size_16_color_FFFFFF_t_70]

输入格式

第一行两个整数n和m，代表n行m列。(1<=n,m<=10)

下面n行每行m个字符,0代表可以通行，1代表不可以通行。

输出格式

如果能从迷宫走出，输出yes，否则输出no。

输入样例

8 8
    00100010
    00100010
    00001100
    01110000
    00010000
    01000100
    01110110
    00001000

输出样例

yes

### 方向数组定义方法： ###

先定一个起点，再写出四个方向关于起点的关系（数组坐标）（本题为上下左右四个方向，八皇后问题就八个方向）本题我自己定义的方向是：右，下，左，上  
图解：  
![在这里插入图片描述][20210403094657898.png]  
代码如下:

#include<iostream>
    using namespace std;
    int v[105][105],j;
    char a[105][105];
    int n,m,s=0;
    int dx[4]= {
        0,1,0,-1},dy[4]= {
        1,0,-1,0}; //方向数组定义：右，下，左，上
    void Position(int x,int y)
    {
        
        if(x==n&&y==m)//递归结束条件
        {
        
            s=1;
            return;//退出递归
        }
        for(int i=0; i<4; i++)//四个方向搜一遍
        {
        
            int nx=dx[i]+x,ny=dy[i]+y;
            if(nx>=1 && ny>=1 && nx<=n && ny<=m && v[nx][ny]==0 && a[nx][ny]=='0')
            {
        
                v[nx][ny]=1;//标记走过
                Position(nx,ny);//在下一个点上在点的四个方向搜一遍
            }
        }
    }
    int main()
    {
        
        cin >> n>>m;
        for(int i=1; i<=n; i++)//输入迷宫
            for(j=1; j<=m; j++)
                cin >> a[i][j];
        Position(1,1);
        if(s)cout << "yes" << endl;
        else cout << "no" << endl;
    }

思路:此题问题是能不能走到终点，所以只要找到一条可以通过的路即可，因此，用广搜法。因为要可以上下左右移动，所以可以用到方向数组。

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

### 扩展：用回溯法求步数 ###

即计算最短的路径(步数)

只需在原代码中进行修改即可

注意要判断是否走得通，走不通输出-1

代码如下：

#include<iostream>
    using namespace std;
    int v[105][105],j,s=0;
    char a[105][105];
    int n,m,ans=10000;
    int dx[4]= {
        0,1,0,-1},dy[4]= {
        1,0,-1,0};//方向数组定义：右，下，左，上
    void Position(int x,int y,int step)
    {
        
        if(x==n&&y==m)//递归结束条件
        {
        
        	s=1;
            ans=min(ans,step);//求出最小的步数
            return;//退出递归
        }
        for(int i=0; i<4; i++)//四个方向搜一遍
        {
        
            int nx=dx[i]+x,ny=dy[i]+y;
            if(nx>=1 && ny>=1 && nx<=n && ny<=m && v[nx][ny]==0 && a[nx][ny]=='0')
            {
        
                v[nx][ny]=1;//标记走过
                Position(nx,ny,step+1);//在下一个点上在点的四个方向搜一遍，并且步数加1
                v[nx][ny]=0;//发现走不通的就回溯
            }
        }
    }
    int main()
    {
        
        cin >> n>>m;
        for(int i=1; i<=n; i++)//输入迷宫
            for(j=1; j<=m; j++)
                cin >> a[i][j];
        Position(1,1,0);
        if(s)
        cout << ans << endl;
        else
        cout<<"-1";
    }

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

### 注意：全局变量和局部变量的影响 ###

这里Position函数中要用局部变量，因为i要变。若用全局变量会报错

## 此为个人笔记，不喜勿喷！ ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUxMjk3OTg3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210403094620328.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUxMjk3OTg3,size_16,color_FFFFFF,t_70
[20210403094657898.png]: https://img-blog.csdnimg.cn/20210403094657898.png