“ 一条路走到黑，不撞南墙不回头”——C++【DFS（深度优先搜索算法）】入门讲解_c++dfs模板

Hello，大家好，我是Amy，好久不见（我真好意思说好久不见）~

虽迟但到，你们一直催更的dfs算法终于来啦~

话不多说，让我们直接进入主题吧！

---

目录

缺点

简介

“地图类” 深度优先搜索

“方案数” 深度优先搜索

“联通块” 深度优先搜索

什么是联通块？

题目+模板套餐

总结

---

缺点

我们先来看一个硬币问题的对比图：

 由此可见，dfs有一个很大的缺点：容易超时，慎用！！！

---

简介

DFS（Depth First Search）简称“深搜”，是个骗分利器得分利器。正如标题所述，这个算法的特点就是： 一条路走到黑，不撞南墙不回头。

通俗地说，即在遍历时，优先选择一条路，往搜索树的深层遍历，当不能继续深入时则返回上一层，选择另一个岔路遍历。

深度优先搜索按照深度优先的方式进行搜索，通俗点说就是 〃一条路走到黑〃。注意，这里的    〃搜索〃是一种穷举的方式，把所有可行的方案都列出来，不断去尝试，直到找到问题的解。     深度优先搜索和递归的区别是：深度优先搜索是一种算法，注重的是思想；而递归是一种基于编程语言的实现方式。深度优先搜索可以用递归实现，也就是说递归是我们用计算机编程语言来实现深度优先搜索这个算法的手段。

深搜核心：设计状态、认准目标

---

下面我们就先来看第一种深搜：地图类深搜

---

“地图类” 深度优先搜索

我们先以这道入门题为例，来给大家看一下DFS大致的框架和模板

入门题（迷宫游戏）

用一个二维数组表示迷宫，其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。需要从起点S出发走到T，每一次只能上下左右移动一步，不能走出地图，不能穿过墙壁，每个点只能通过一次。请找出一条从起点到终点的路径。

模板如下：（模板的备注解释我会在另一篇讲DFS的文章中继续讲解）

//其实DFS的理解不难，就是比较废手，代码比较长，不可怕
#include<bits/stdc++.h>//备注我就不敲了，时间有限，十分抱歉
using namespace std;
long long n,m;
string maze[110];
bool vis[110][110];
bool in(int x,int y){
	if(0<=x && x<n && 0<=y && y<m) return true;
	else return false;
}
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
bool dfs(int x,int y){
	if(maze[x][y]=='T') return true;
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(in(tx,ty) && maze[tx][ty]!='*' && vis[tx][ty]==0){
			if(dfs(tx,ty)) return true;
		}
	}
	return false;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>maze[i];
	int x,y;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(maze[i][j]=='S') x=i,y=j;
		}
	}
	if(dfs(x,y)){
		cout<<"Yes";
	}
	else cout<<"No";
    return 0;
}

这是最基础的一种——地图路径判断

---

“方案数” 深度优先搜索

同样是一道题目+模板送给大家~

给定一个m行n列的迷宫图案，请问从S点到T点存在一条的通路数。（只能沿上、下、左、右四个方向行走，一次只能走一步；其中‘.’表示可以通行；‘*’表示不能够通行）。

不难看出，这道题和上面那道题十分相似，唯一的区别就是：前面那道题是要求路径，而这道题是要求路径的数量，也就是方案数。

模板：
 

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans;
string maze[110];
bool vis[110][110];
bool in(int x,int y){
	if(0<=x && x<n && 0<=y && y<m) return 1;
	else return 0;
}
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//上下左右四个方向
void dfs(int x,int y){
	if(maze[x][y]=='T'){
		ans++;
		return ;
	}
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(in(tx,ty)==1 && maze[tx][ty]!='*' && vis[tx][ty]==0){
			dfs(tx,ty);
		}
	}
	vis[x][y]=0;
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>maze[i];
	int x,y;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(maze[i][j]=='S') x=i,y=j;
		}
	}
	dfs(x,y);
	cout<<ans;
    return 0;
}

---

“联通块” 深度优先搜索

这类题目是这篇文章中最难的一类题目，但是不用害怕，理解起来并不困难。我先来解释一下联通块的意思。

什么是联通块？

联通块，顾名思义，就是相互联通的（东西）。究竟是怎样相互联通呢，具体还得看题目描述。

假如题目描述是这样的：开学时，Amy所在的学校在操场上铺了一块m×n的草坪，草坪是由一小块一小块草皮连接起来的。由于经常有人踩踏草坪，经过一年的时间，中间一些小草皮变成了空地，Amy想知道还剩下几块连接在一起的草皮块（上、下、左、右相邻的小草皮看成是一个块）。

那么这道题中“上、下、左、右相邻的小草皮看成是一个块”这句话就是重点，说明题目中的草皮块是上下左右四个方向相互联通的。

例如这样的几块草皮块就是互相连通的，看作是一整块：

题目+模板套餐

开学时，Amy所在的学校在操场上铺了一块m×n的草坪，草坪是由一小块一小块草皮连接起来的。由于经常有人踩踏草坪，经过一年的时间，中间一些小草皮变成了空地，Amy想知道还剩下几块连接在一起的草皮块（上、下、左、右相邻的小草皮看成是一个块）。其中，‘*’表示草皮，‘.’表示空地。

模板：

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans;
string maze[110];
bool vis[110][110];
bool in(int x,int y){
	if(0<=x && x<n && 0<=y && y<m) return 1;
	else return 0;
}
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
void dfs(int x,int y){
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(in(tx,ty)==1 && maze[tx][ty]=='*' && vis[tx][ty]==0){
			dfs(tx,ty);
		}
	}
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>maze[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(maze[i][j]=='*' && vis[i][j]==0) ans++,dfs(i,j);
		}
	}
	cout<<ans;
    return 0;
}

---

总结

DFS看起来代码量比较大，很吓人，但其实理解起来非常容易。只要多加练习，我相信你一定可以很好的掌握这个算法~

这篇文章因为是赶时间写出来的，比较潦草，我日后也会继续做进一步的修改~有什么问题请私信我，我会及时修改达~

您的支持就是我最大的动力~动动手指点个赞，让更多的人看到我的作品~