前言：如果不是时间限制，他早已成神

深度优先搜索（DFS）

1. 什么是深度优先搜索？

深度优先搜索 是一种用于遍历或搜索树/图数据结构的算法。

• 核心思想：“不撞南墙不回头”。
  • 从一个顶点开始，沿着一条路径一直走到底。
  • 当无法继续前进（遇到死胡同或已访问过的节点）时，返回上一个岔路口（回溯），选择另一条路继续走。
• 数据结构基础：递归（系统栈）或显式栈。

dfs算法具体算法描述为：

选择一个起始点 作为 当前结点，执行如下操作：

a. 访问 当前结点，并且标记该结点已被访问，然后跳转到 b；

b. 如果存在一个和 当前结点 相邻并且尚未被访问的结点 ，则将 设为 当前结点，继续执行 a；

c. 如果不存在这样的 ，则进行回溯，回溯的过程就是回退 当前结点；

上述所说的 当前结点 需要用一个栈来维护，每次访问到的结点入栈，回溯的时候出栈。除了栈，另一种实现深度优先搜索的方式是递归，代码更加简单，相对好理解。

DFS的核心特征

1.递归性

问题可以分解为子问题

子问题的解决方式与原问题相同

有明确的终止条件

2.回溯性

当前路径不通时，返回上一步

尝试其他可能的选择

记录和恢复状态

3.完整性

保证访问所有可能的路径

不会重复访问节点

一定能找到解（如果存在）

2. 核心框架：递归三要素

在C++中，DFS通常以递归函数的形式实现。一个标准的DFS函数包含以下三个要素：

1. 终止条件 (Base Case)：什么时候找到了答案？什么时候越界了？什么时候遇到了障碍？
2. 标记现场 (Mark)：当前节点正在被访问，为了防止走回头路，通常需要标记为“已访问”。
3. 递归探索 (Recursive Call)：向所有可能的方向（上、下、左、右，或子节点）进行探索。
4. 恢复现场 (Backtracking / Unmark)：这是回溯的精髓。当子递归返回后，需要将当前节点的状态恢复原样，以便让父节点的其他分支能够正确使用这个节点。

4. DFS例题

OD1821 冰河世纪-小拨鼠de坚果1

这是最经典的DFS场景

思路

遍历每一个格子。如果遇到起始点“@”，就启动DFS，如果可以行走（不为冰川“#”），就向相邻方向递归，如果碰到坚果“.”，坚果总数+1，最后输出坚果总数

代码

递归求解

#include <iostream>
using namespace std;
int n,m,cnt,sx,sy;
char g[55][55];//存储矩阵图 
bool vis[55][55];//标记是否已经走过 
int dfs(int x ,int y){
    if(x<1||y<1||x>n||y>m)return 0;//出界返回0 
    if(g[x][y]=='#')return 0;//#不能走 
    if(vis[x][y])return 0;//已经访问过的点跳过 
    vis[x][y]=true;//走过去，并打上标记 
    return dfs(x-1,y)+dfs(x,y+1)+dfs(x+1,y)+dfs(x,y-1)+1;
    //返回4个方向的值再加上自身(x,y)点的数,即+1 
}
int main(){
	cin>>m>>n;//这类题输入时候一定要注意行列顺序
	for(int i=1;i<=n;i++){//输入矩阵图 
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='@'){//标记出发点 
				sx=i,sy=j;
			}
		}
	}
	cout<< dfs(sx,sy);//根据起始点，dfs直接输出答案	
	return 0;
}

上述递归方式可以改写为以下形式：

#include <iostream>
using namespace std;
int n,m,cnt,sx,sy;
char g[55][55];
bool vis[55][55];
void dfs(int x ,int y){
    if(x<1||y<1||x>n||y>m)return;
    if(g[x][y]=='#')return;
    if(vis[x][y])return;
    cnt++;//经过的点，计数器加1 
    vis[x][y]=true;//标记当前点，以免下次重复计算 
    dfs(x-1,y);//往上走过去 
    dfs(x,y+1);//往右走过去
    dfs(x+1,y);//往下走过去
    dfs(x,y-1);//往左走过去   
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='@'){
				sx=i,sy=j;
			}
		}
	}
	dfs(sx,sy);//无返回形式递归 
	cout<<cnt;//递归结束后，答案记录在计数器cnt 
	return 0;
}

把4个递归改写为for循环，这样更符合dfs的一般格式

#include <iostream>
using namespace std;
int n,m,cnt,sx,sy;
int dx[]={0,-1,0,1,0};
int dy[]={0,0,1,0,-1};
char g[55][55];
bool vis[55][55];
bool check(int x,int y){//检查(x,y)是否可以走过去（是否合法） 
	if(x<1||y<1||x>n||y>m)return false;//出界 
    if(g[x][y]=='#')return false;//障碍物不能走 
    if(vis[x][y])return false;//已经访问不能重复计算 
    return true;//合法的(x,y) 
}
void dfs(int x,int y){
	cnt++;
	vis[x][y]=true;
	for(int i=1;i<=4;i++){//四个方向上递归
		int newx=x+dx[i];
		int newy=y+dy[i];
		if(check(newx,newy)){//递归前先检查是否合法 
			dfs(newx,newy);	
		}					
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='@'){
				sx=i,sy=j;
				g[i][j]='.';//注意是否需要修改起点参数(本题可以不需要） 
			}
		}
	}
	if(check(sx,sy))dfs(sx,sy);//递归前先检查是否合法（本题这里可以不需要check） 
	cout<<cnt;
	return 0;
}

也可以把vis的标记合并到g数组中去

#include <iostream>
using namespace std;
int n,m,sx,sy;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int cnt;//全局变量 
char g[105][105];
void dfs(int x,int y){//当前的点(x行，y列） 
	if(x<1 || x>n || y<1 || y>m) return;
	if(g[x][y]=='#')return ;	
	cnt++;//计数 
	g[x][y]='#';//打上标记 
	for(int i=0;i<4;i++)	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		dfs(nx,ny);
	}
}
int main(){
	cin>>m>>n;//输入 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='@'){
				sx=i;sy=j;//记住起点 
			}
		}
	}
	dfs(sx,sy);//从起点开始搜索 
	cout<<cnt;
	return 0;
}

5. 剪枝优化

DFS 的时间复杂度通常很高（指数级）。剪枝 是在搜索过程中提前终止那些不可能产生可行解的分支的技术。

if(step>=ans){
	return;
}

这句话的意思是如果当前步数已经大于最优步数，就返回

6. 常见错误与调试技巧

1. 栈溢出：

   • 现象：递归层数过深（例如 1e5 层），导致 Segmentation Fault。
   • 解决：对于线性结构或极深图，改用 显式栈（迭代） 代替递归。

2. 忘记恢复现场：

   • 在需要回溯的场景（如全排列、N皇后），如果忘记 pop_back 或重置 used，会导致状态混乱。
   • 调试：在递归入口和出口打印 path 或状态，观察是否符合预期。

3. 死循环：

   • 通常是因为没有正确标记已访问节点，导致在两个节点间来回跳跃。
   • 解决：确保在进入递归前标记，或者使用 visited 集合并检查。

4. 引用传递陷阱：

   • 如果在递归中修改了通过引用传递的参数，并且需要回溯，务必在返回前恢复原状。
   • 如果不需要回溯（如岛屿问题中直接修改原数组），则无需恢复。

9. 总结：DFS 解题模板

void dfs(状态参数, 全局引用结果) {
    // 1. 终止条件
    if (满足结束条件) {
        记录结果;
        return;
    }
    
    // 2. 遍历所有可能的选择
    for ( 枚举每一个扩展状态 ) {
        // 3. 剪枝 (可选)
        if (不合法) continue;
        
        // 4. 做选择 (标记现场)
        
        // 5. 递归进入下一层
        dfs(新状态, 结果);
        
        // 6. 撤销选择 (恢复现场) —— 回溯
    }
}

掌握 DFS 的关键：理解 “递” 与 “归” 的过程，以及 “状态” 是如何在栈帧中传递和变化的。

0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6