一、深度优先搜索概念:
它从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直至找到最终的解
二、关于DFS:
(1)dfs常用于求连通块，
(2)对于DFS，一般采用递归方式，隐式地利用栈进行计算。
(3)深搜(DFS)耗费空间比广搜(BFS)小，因为深搜(DFS)是一种深度的搜索，复杂度与空间深度成正比;而广搜(BFS)是通过遍历每个状态进行搜索，复杂度与状态数有关。可想而知状态数必定大过递归的深度，所以DFS比BFS更加节省空间。
(4)深搜和广搜图示:
深搜:↓
广搜:↓
三、例题:迷宫问题:
有一天，傻子A一个人去迷宫玩，但是他的方向感并不是很好，所以他很快就迷路了，哎哟喂，这可把他的小伙伴小Z给急死了，小Z得知后立即去解决傻子A，小Z来之前，做足了调研，弄到了迷宫的地图，现在问题来了：小Z要用最快的速度去解救傻子A。小Z拥有的地图是一个n行m列的单元格（0< n , m <= 50），单元格上要么是空地，要么是障碍物，我们的任务是帮小Z找一条从迷宫起点，通往小Z所在位置的最短路径，注意：障碍物是不能走的！小A是不动的，规定0表示空地、1表示障碍物，2表示傻子A所在的坐标。
样例输入:
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 2 0
0 0 0 1
样例输出：
7
#include<iostream>
#define MAXN 51
using namespace std;
int map[MAXN][MAXN]; //矩阵存储地图
bool book[MAXN][MAXN]={false}; //初始化false为没走过
int Endx,Endy; //终点坐标
int n,m; //n行m列
int minn=999999; //初始比较量
int next[4][2]={
{ 1, 0}
, { 0,-1}
, {-1, 0}
, { 0, 1}
, }; //右、下、左、上
void dfs(int x,int y,int step)//坐标(x,y)表示当前坐标,step表示当前执行了几步
{//遍历四种方向
for(int i=0;i<4;i++)
{//计算新的坐标
int gx=x+next[i][0];
int gy=y+next[i][1];
if(gx<0||gx>n-1||gy<0||gy>m-1)
{//坐标越界则换方向
continue;
}
if(gx==Endx && gy==Endy)
{//走到终点时
minn=min(step+1,minn);
}
if(book[gx][gy]==false && map[gx][gy]==0)
{//如果没有走过且为空地，则执行
book[gx][gy]=true;//标记
dfs(gx,gy,step+1); //传入新坐标,步数加一
}
}
}
int main()
{
//地图的输入
cin >> n >> m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin >> map[i][j];
if(map[i][j]==2)
{//值为2的坐标点赋值给Endx和Endy
Endx=i,Endy=j;
}
}
book[0][0]=true;//标记起始点
dfs(0,0,0);
cout << minn << endl;
return 0;
}
京公网安备 11010502036488号