搜索算法之深度优先搜索和广度优先搜索-蒲公英云

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

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

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

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

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

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

输入：

数据的第一行给你两个数：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：

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

代码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);
    }
}