欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

迷宫问题----深搜经典问题

程序员文章站 2022-05-20 20:49:27
...

迷宫问题是深搜算法的最常见也是最基础的题型之一

深搜大家应该都已经理解了
如果还不知道深搜是什么可以参考我之前的一篇:深搜讲解
我们把我们撞南墙才回头的思想运用到我们的迷宫问题中
就可以理解为:

从起点开始随便找一条路开始走
走到了终点或没有继续向前的格子就回头

用最简单的2x2迷宫来举例

如果我们设起点是(1,1)这个点,终点是(2,2)这个点,
障碍物是(2,1)这个点。

我们从起点开始可以选择去(1,2)或者去(2,1),但后者是障碍物,所以我们只能选择(1,2),到了这个点我们可以只能去(2,2)(因为走过的地方不能再走),所以我们到达了终点,此时我们回头去寻找另外的路径。但我们发现,不管退到前面的哪一步(包括退回到起点),我们都没有其他的路径选择,所以最后的答案就只有一条。
(如果没有理解,建议先把上一篇讲解深搜的先理解透彻)。
接下来我们直接看code
点击查看题目>>来自洛谷

#include <bits/stdc++.h>

using namespace std;
int n,m,t;
int a[10][10]; //标记x,y这个点是否是障碍物或已经被走过
int nowi,nowj;//现在走到哪里了,即现在的坐标
int toi,toj;//终点坐标
int flag;//有几种路径,即最后输出的答案
void work(int x);//运行函数
int main()
{
    while(cin >> n >>m >> t)
    {
        flag=0;
        cin >> nowi >> nowj >> toi >> toj;
        a[nowi][nowj]=1;//对起点进行标记
        for(int i=1; i<=t; i++)
        {
            int x,y;
            cin >> x >> y;
            a[x][y]=1;//给障碍物进行标记
        }
        work(1);
        cout << flag << endl ;
        a[nowi][nowj]=0;//清楚此次起点的标记
        memset(a,0,sizeof(a));//最后清0数组,具体是清楚障碍物标记的地方
    }
    return 0;
}
void work(int x)
{
    if(nowi==toi&&nowj==toj)
    //达到了终点,flag++,并且不再进行函数的其他操作,其实可以++完直接return
    {
        flag++;
    }
    else
    {//这里的x为1,2,3,4的操作可以根据自己喜好来调换
        if(x==1)//把它移动向行数增加的那一格
        {
            if(a[nowi+1][nowj]==0&&nowi+1<=n)
            {
                a[nowi+1][nowj]=1;//标记这个位置
                nowi++;
                work(1);
                nowi--;
                a[nowi+1][nowj]=0;//别忘记这里要清楚标记
            }//如果不懂这种if函数为什么这样写,可以先理解上一篇的代码,有详细讲解
        }
        if(x==2)//把它移动向列数增加的那一格
        {
            if(a[nowi][nowj+1]==0&&nowj+1<=m)
            {
                a[nowi][nowj+1]=1;
                nowj++;
                work(1);
                nowj--;
                a[nowi][nowj+1]=0;
            }
        }
        if(x==3)//把它移动向行数减少的那一格
        {
            if(a[nowi-1][nowj]==0&&nowi-1>=1)
            {
                a[nowi-1][nowj]=1;
                nowi--;
                work(1);
                nowi++;
                a[nowi-1][nowj]=0;
            }
        }
        if(x==4)//把它移动向列数减少的那一格
        {
            if(a[nowi][nowj-1]==0&&nowj-1>=1)
            {
                a[nowi][nowj-1]=1;
                nowj--;
                work(1);
                nowj++;
                a[nowi][nowj-1]=0;
            }
        }
        if(x+1<=4)//不能加else哦,理解一下
        /*不管是不满足以上条件,还是从上面条件运行完再出来,
        都要进行它的下一项(如果没有超出边界的话)*/
            work(x+1);
    }
}