广/深度优先搜索(bfs/dfs)例题：2020neu校赛热身赛：找猫猫

Ava ·

更新时间:2024-09-20

· 618 次阅读

Problem: 找猫猫
Time limit: 1s Mem limit: 64 MB AC/Submission: 32/169
Problem Description
猫猫和嘟嘟一起打游戏，猫猫被困在了M点不能移动，每一秒减少一个单位的HP，需要队友嘟嘟来救。但是现在嘟嘟不在猫猫旁边，而是在远离猫猫的另一个D点。当猫猫的HP变成负数之后，猫猫的人物就会死亡，而猫猫就会不高兴。为了让猫猫能继续玩下去，嘟嘟需要马上到M点去救猫猫（嘟嘟到达后可以让猫猫的HP增加并且可以离开M点）。

现在给你这个n*m的游戏地图， D代表嘟嘟的位置，M代表猫猫的位置，*代表可以走的路，#代表不能翻越的墙。已知现在猫猫的HP为t个单位，嘟嘟每1秒只能移动1个格子，只能走上下左右四个方向（不能斜着走，即四联通）。

现在问你，嘟嘟能不能在猫猫HP变为负数之前到达M点？如果能到达，请输出猫猫最小损失的HP。不然，游戏结束，猫猫很生气，嘟嘟会跪机械键盘的，所以就要输出一行字符串：“OMG! DUDU is bound to Kneel keyboard”(没有引号）。

Input
第一行一个整数T，代表有T组数据。

每组数据的第一行有三个整数m, n, t，分别表示地图的行数、地图的列数和猫猫的HP。 (0<=m,n<=10 0<=t<=100)
接下来有m行数据，每行n个字符，代表一个mn的矩阵，矩阵有且仅有’D’ ’M’ ‘’ ‘#’字符组成（没有引号）

Output
如果嘟嘟能在猫猫HP变为负数之前到达M点，则输出猫猫损失的最小HP。

否则输出“OMG! DUDU is bound to Kneel keyboard”（没有引号）

Sample Input
2
3 3 10
D**
#
#M*
3 3 2
D**
#
#M*
Sample Output
5
OMG! DUDU is bound to Kneel keyboard
解1：bfs广搜
分析：
广搜的核心是在每一个当前的起点找到可以扩展的所有点，
再把扩展出的所有点作为新的起点，继续扩展，扩展1次则step+1，
类比等高线，可以把广搜看作找出图的等step线，然后判断终点在哪条等step线上
因此，只要扩展出的是目的地，此时记录的step一定是最少的


```cpp
#include//万能头文件
using namespace std;
struct note
{
    int x;
    int y;//坐标
    int f;//本题不需要求路径，可忽略
    int s;//步数
}que[144];//队列数组
int a[12][12];//记录图
const int dx[4]={1,-1,0,0};//四个方向移动
const int dy[4]={0,0,1,-1};
int main()
{
    iostream::sync_with_stdio(0);//关同步，加快输入速度
    int T;
    cin>>T;
    while(T--)
    {
        memset(que,0,sizeof(que[0])*144);//初始化
        memset(a,0,sizeof(a[0][0])*144);
        int m,n,HP;
        cin>>m>>n>>HP;
        int i,j,k,t;
        int sx,sy,ex,ey;//开始，结束点
        for(i=1;i<=m;i++)
        {
            for(j=1;j>c;
                if(c=='*')
                {
                    a[i][j]=1;
                }
               else if(c=='D')
                {
                    sx=i;
                    sy=j;
                }
               else if(c=='M')
                {
                    ex=i;
                    ey=j;
                    a[i][j]=1;
                }
            }
        }
        int tx=sx,ty=sy,head=1,tail=2,flag=0;//tx,ty是当前的坐标，head是起始点，tail是扩展出的点，flag记录是否到终点
        que[head].x=sx;//对头初始化
        que[head].y=sy;
        while(head<tail)//队列不为空
        {
            for(i=0;i<4;i++)//从当前点开始遍历四个方向
            {
                tx=que[head].x+dx[i];//head点可向4个方向走，成为当前驻点
                ty=que[head].y+dy[i];
              if(a[tx][ty])//驻点如果不是走过的点、四周围墙和障碍物
              {
                a[tx][ty]=0;//标记为走过的点
                que[tail].x=tx;//驻点入队
                que[tail].y=ty;
                que[tail].f=head;//路径
                que[tail].s=que[head].s+1;
                tail++;//记录下一个点
              }
              if(ex==tx&&ey==ty)
                {
                flag=1;//到终点了
                break;
                }
            }
             if(flag==1)
                break;
            head++;//这里非常重要，在一个起点扩展完4个点后，这4个点又作为新起点再扩展新的点
        }
        if(head==tail||HP<que[tail-1].s)//如果嘟嘟四周都是围墙呢？因此要判断head?=tail
        cout<<"OMG! DUDU is bound to Kneel keyboard"<<endl;
        else
            cout<<que[tail-1].s<<endl;
    }
    return 0;
}

解2：深搜dfs
分析：深搜的核心是分解成当下怎么做和下一步怎么做，当下有4个可能延展方向，选一个方向作为新的当下。重复此过程。

#include
using namespace std;
int m,n,ex,ey,step,ans;//行列，终点，当前路径步数，最小步数
bool a[13][13];//记录地图
const int X[4]={1,-1,0,0};//四个方向
const int Y[4]={0,0,1,-1};
void dfs(int sx,int sy,int step)//当前起点与该路径步数
{
    int tx,ty;//当前扩展出的坐标
    if(step>=ans)//剪枝，如果已经比当前的最短路径长了，就没必要再搜了
        return;
    if(ex==sx&&ey==sy)
    {
        ans=step;//记录到达终点更短的步数
        return;
    }
    for(int i=0;i>T;
    while(T--)
    {
        ans=999999;
        memset(a,false,sizeof(a));
    int HP,sx,sy;
    cin>>m>>n>>HP;
    int i,j,k;
    for(i=1;i<=m;i++)
    {
        for(j=1;j>c;
            if(c=='*')
            {
                a[i][j]=1;
            }
            else if(c=='D')
            {
                sx=i;
                sy=j;
            }
            else if(c=='M')
            {
                ex=i;
                ey=j;
                a[i][j]=1;
            }
        }
    }
    dfs(sx,sy,0);
     if(HP<ans)
       cout<<"OMG! DUDU is bound to Kneel keyboard"<<endl;
    else
        cout<<ans<<endl;
    }
    return 0;
}

对比两种算法：bfs更快，因为它不用返回到前一步，第一次到达即最短路径，但是可能会更占内存；dfs慢，但可以记录所有路径，可以解决需要枚举所有排列的问题，而且内存可能占的更少

作者：仝竞奇

深度优先搜索 dfs

1024 个赞