广/深度优先搜索(bfs/dfs)例题：2020neu校赛热身赛：找猫猫dfs,bfs,队列tongjingqi的博客-

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<bits/stdc++.h>//万能头文件 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<=n;j++) { /*先转换图，走过的路四周围墙和障碍物用0代替，                  可走的路用1代替，可省去一个book数组*/ char c;                 cin>>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<bits/stdc++.h> 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<4;i++)//遍历四个方向 {         tx=sx+X[i];//向四个方向中的一个方向扩展         ty=sy+Y[i]; if(a[tx][ty])//如果不是障碍物，边缘或已走过的路 {             a[tx][ty]=0;//记录已经走过 dfs(tx,ty,step+1);//该点作为起点，向下扩展一步             a[tx][ty]=1;//执行到这步说明当前步作为起点的探索失败了，但其他搜索路径可能会经过该点，因此要还原 } } return; } int main()//主函数同理 {     iostream::sync_with_stdio(0); int T;     cin>>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<=n;j++) { char c;             cin>>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慢，但可以记录所有路径，可以解决需要枚举所有排列的问题，而且内存可能占的更少