搜索算法之深度优先搜索和广度优先搜索

梦里梦外; 2022-06-01 06:36 372阅读 0赞

所谓深度优先搜索：就是一条道走到黑，不碰南墙不回头的那种。

广度优先搜索：就是从你所站的位置向周围扩散性的搜索，通俗来讲，就是你在黑夜里眼睛掉了，你肯定是趴在地上，手向四周摸索，摸不到会到下一步摸索。

一道简单的例题的两种不同的做法：

问题描述：（自己编的![大笑][laugh.gif]，绝对原创），小明和女神小红一起出去游玩，偶然发现一座上古迷宫（里面可能有科学不能解释的神奇物品），好奇心特别重的小红想着里面有能让自己变漂亮的神奇药水（女生都比较爱美），于是想进去寻找，小明也想进去保护女神，但是俩人带了超多的东西，小红执意让他留下来看东西，自己一人前往。可是路痴的她没走多久就迷路了，又怕黑的她向小明求救，（假如可以听的到），小明为救女神肯定要走最短的路径，但是该如何走呢？

输入：

数据的第一行给你两个数：n,m,（0<n,m<100)表示迷宫的长和宽，然后输入迷宫，接下来是迷宫的入口和此时女神所在的位置,小明在迷宫内只能上下左右移动。

输出：解救女神的最小步数。

样例1：

输入：7 7
    1 0 1 1 1 1 1
    1 0 1 0 0 0 0
    1 0 0 0 0 0 1
    1 0 0 0 1 0 1
    1 1 0 0 0 0 1
    1 1 0 1 0 1 1
    1 1 1 1 1 1 1
    0 1 5 4
    输出：8

样例2：

输入：
    5 4
    0 0 1 0
    0 0 0 0
    0 0 1 0
    0 1 0 0
    0 0 0 1
    0 0 3 2
    输出：7

自己瞎编的一道题，用不同的方法做的，学了好久的搜索，其中队列总是不会，然后通过两种不同的做法来完成这道题

代码1：深度优先搜索

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>
    #include<algorithm>
    #define min(a,b)a>b?b:a;
    using namespace std;
    int m,n,st_x,st_y,end_x,end_y,ans;//分别为迷宫的起点和终点
    int migong[101][101];//定义一个迷宫地图
    void dfs(int x,int y,int s)//用s表示当前所走的路
    {
        if(x<0||y<0||x>=m||y>=n||migong[x][y])//如果出界或遇到墙则返回
            return;
        if(x==end_x&&y==end_y)//到达目的地搜索结束
        {
            ans=min(ans,s);
            return ;
        }
        s++;
        migong[x][y]=1;//走过的路变为墙，防止重复走
        dfs(x+1,y,s);//四个方向进行搜索
        dfs(x-1,y,s);
        dfs(x,y+1,s);
        dfs(x,y-1,s);
        migong[x][y]=0;//变为原来的样子
    }
    int main()
    {
        while(scanf("%d%d",&m,&n)!=EOF)
        {
            int i,j;
    
            for(i=0; i<m; i++)
            {
                for(j=0; j<n; j++)
                {
                    scanf("%d",&migong[i][j]);
                }
            }
            scanf("%d%d%d%d",&st_x,&st_y,&end_x,&end_y);
            ans=n*m;//走的步数最多为n*m
            dfs(st_x,st_y,0);
            printf("%d\n",ans);
        }
        return 0;
    }

代码2：广度优先搜索

#include<stdio.h>
    #include<string.h>
    #include<queue>
    #include<math.h>
    #include<stdlib.h>
    #include<algorithm>
    using namespace std;
    int n,m,st_x,st_y,end_x,end_y;
    int map[101][101];
    int mark[101][101];//标记地图
    int move_x[4]= {0,0,1,-1};//四个移动方向
    int move_y[4]= {1,-1,0,0};
    struct node//定义一个队列结构体
    {
        int x,y,step;
    } a,next;
    int check(int x,int y)//判断是否能通过
    {
        if(x<0||y<0||x>=m||y>=n||mark[x][y]||map[x][y])
            return 1;
        else
            return 0;
    }
    int bfs()
    {
        int i;
        queue<node>Q;//创建一个队列
        a.x=st_x;
        a.y=st_y;
        a.step=0;
        mark[st_x][st_y]=1;
        Q.push(a);//向队列中添加一个元素a
        while(!Q.empty())//队列为空则返回真，非空返回假
        {
            a=Q.front();//返回队列里的头部元素
            Q.pop();// 删除队列的第一个元素
            if(a.x==end_x&&a.y==end_y)
                return a.step;
            for(i=0; i<4; i++)
            {
                next.x=a.x+move_x[i];
                next.y=a.y+move_y[i];
                if(check(next.x,next.y))
                    continue;
                else
                    next.step=a.step+1;
                Q.push(next);
            }
        }
        return 0;
    }
    int main()
    {
        while(scanf("%d%d",&m,&n)!=EOF)
        {
            int i,j,ans;
            memset(mark,0,sizeof(mark));
            for(i=0; i<m; i++)
            {
                for(j=0; j<n; j++)
                {
                    scanf("%d",&map[i][j]);
                }
            }
            scanf("%d%d%d%d",&st_x,&st_y,&end_x,&end_y);
            ans=bfs();
            printf("%d\n",ans);
        }
    }

[laugh.gif]: /images/20220601/4b17d8ed19c549f39c1de94c9a4ee9ff.png