BFS 广度优先搜索参见 BFS

一、什么是DFS？

1. 核心思想

深度优先搜索算法（DFS）是一种用于遍历或搜索树或图的算法，它的核心思想是，一条路走到底，不撞墙不回头，即“深度优先”。

2. DFS和BFS的不同点

（1）DFS是用来解决寻求多个解的问题；而BFS是搜寻最优解，比如最短路径问题。
（2）DFS搜索需要全数搜索，需要记录数据，计算量大，需要剪枝以避免超时；而BFS以全面“铺开”搜索为目的，举例最短路径问题，只要记录最小值即可，计算量小。

二、DFS通用模板

注意： 此模板需要根据题目灵活运用，切忌生搬硬套！

bool check(参数) 
{
  //通常是判断是否走过此位置（个人习惯用二维数组done[][]记录，0代表未走，1代表已走）
  //或者是走迷宫问题等，需要判断是不是迷宫的"墙"。
    if(满足条件)
        return true ;
    return false;
}
  
void dfs(int step)
{
        if() //判断边界
        {
            相应操作
        }
    //在当前点上下左右走尝试每一种可能，需根据题目变通
        for(int i=0;i<4;i++)
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}

三、例题

题目洛谷B3625 迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n*m矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 (1, 1)的位置，问能否走到 (n, m) 位置。

输入格式

第一行，两个正整数 n,m。
接下来 n 行，输入这个迷宫。每行输入一个长为 m 的字符串，# 表示墙，. 表示空地。

输出格式

仅一行，一个字符串。如果机器猫能走到 (n, m)，则输出 Yes；否则输出 No。

样例 #1

样例输入 #1

3 5
.##.#
.#...
...#.

样例输出 #1

Yes

个人题解

#include <bits/stdc++.h>
using namespace std;
char Map[101][101]; 
int done[101][101]={0}; //在地图上走的问题，都必须加上done这类标记数组，避免重复走导致程序死循环
int dy[4]={0,1,0,-1}; //(dx,dy)对应了上下左右四个方向
int dx[4]={1,0,-1,0};
bool flag = false;  //标记是否到达终点，若到达变为true，方便后面剪枝优化
int n,m;
int check(int x, int y)
{
	if(done[x][y]==1)  //已经走过该格子，不能再走上去
		return 0;
	if(Map[x][y]=='#') //迷宫的墙，不能走
		return 0;
	return 1;
}
void dfs(int x, int y)
{
	if(x==n&&y==m)  //判断是否到达终点
	{
		flag = true;
	}
	if(flag) 
		return ;
	
	if(x<1 || x>n ||y<1 || y>m)  //判断边界
		return ;
	for(int i=0;i<4;i++)  //遍历上下左右四个方向
	{
		int nowx = dx[i] + x; //定义当前（接下来）要走的格子
		int nowy = dy[i] + y;
		if(check(nowx,nowy))
		{
			done[x][y]=1;  //把先前的格子设为"已走过"
			dfs(nowx,nowy); 
          //此处不用回溯done[x][y]=0，不然会超时。
          //但是，如果题目问"从某点出发到某点走过路径的最大值"，那就需要回溯了
		}
	} 
}
int main()
{
  // 输入部分
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cin>>Map[i][j];
	}
	//题目给出从(1,1)走
	dfs(1,1);
  //输出部分
	if(flag)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}