概述
所谓深度优先搜索（以下称为dfs，depth first search），这个高尚的名字，它是什么呢？
我认为，他是一种借助计算机计算能力的枚举。
是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
剪枝，就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。形象地看，就好像剪掉了搜索树的枝条，故称之为“剪枝”。
from csdn
但是他又和普通枚举有什么区别呢？
dfs是基于递归实现的，从名字来看，这很能体现dfs的深度特点。
所以，dfs会从初态一直选择下面的其中一个状态扩展（体现为搜索树上的一个儿子），一直扩展到叶子节点（终态）。dfs的这种深度使他可以更快地接近目标
而普通枚举通常而言由于枚举方向的不确定性（或不易确定）而不方便进行枚举
是不是很不好理解？
来看一道题
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * nn∗n的格点组成，每个格点只有2种状态，..和 # ，前者表示可以通行，后者表示不能通行。
同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点AA走到点BB，问在不走出迷宫的情况下能不能办到。
如果起点或者终点有一个不能通行(为#)，则看成无法办到。
这是经典的走地图问题，为什么不好用普通枚举做呢？
如果用普通枚举，那么最好的方法就是设f[i][j]表示可以从i到j，最后枚举两两点，再从中间寻找一个中介点进行扩展（dp思想）
但是这样浪费也太多了，有些点完全八竿子打不着，但是我们还是要枚举。
如果用dfs，它每次只会尝试一条路径，每一步之间当然是很好确定的，降低了浪费和实现难度。
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int t,n;
bool vis[N][N];
int sx,sy,ex,ey;
const int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
bool check(int x,int y){
if(x<1||x>n||y<1||y>n||vis[x][y]) return false;
else return true;
}
void readin(){
cin>>n;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
char ch;
cin>>ch;
if(ch=='#') vis[i][j]=1;
}
}
cin>>sx>>sy>>ex>>ey;
sx++,sy++,ex++,ey++;
}
bool dfs(int x,int y){
if(x==ex&&y==ey){
return true;
}
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(check(nx,ny)){
vis[nx][ny]=1;
bool ret=dfs(nx,ny);
if(ret) return true;
vis[nx][ny]=0;
}
}
return false;
}
int main(){
cin>>t;
while(t--){
readin();
bool ret=dfs(sx,sy);
cout<<(ret?"YES\n":"NO\n");
}
}
众所周知，dfs还有一个兄弟叫bfs，我简单罗列了他们的区别
| X | 实现 | 适用场景 | 思想区别 |
|---|---|---|---|
| dfs | 递归 | 一步步确定的问题，有前后依赖性 | 执着往下走，这使得有时dfs可能会有很大损耗（例如：网络流FF） |
| bfs | 队列 | 广泛用于图上，或者可以转换为图的问题 | 一层层考虑，在一般没有分层这个概念时不适用（例如：枚举全排列） |
结构
一般的dfs结构
void dfs(参数){
if(边界){
操作
return;
}
for(下一个状态){
if(判断状态合法){
标记
dfs(下一个)
取消标记
}
}
return;
}
请注意边界条件，如果不正确很有可能引起递归爆栈MLE
经典应用
1.杂项
普通枚举可以解决的大部分问题dfs也可以解决。通常效率相差不大但dfs思想更为清晰（不过递归会带来常数上的损耗）。
2.图上求联通块
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 \(N\times M(1\leq N\leq 100, 1\leq M\leq 100)\) 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。
只需枚举每一个点，以此扩展即可。
#include<bits/stdc++.h>
using namespace std;
char mp[101][101];
bool vit[101][101];
int dx[8]={0,0,-1,-1,-1,1,1,1};
int dy[8]={1,-1,-1,0,1,-1,0,1};
int n,m;
bool check(int x,int y)
{
if(x<1||x>n||y<1||y>m||mp[x][y]=='.'||vit[x][y])
{
return 0;
}
else
{
return 1;
}
}
void dfs(int x,int y)
{
vit[x][y]=1;
for(int i=0;i<8;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(check(nx,ny)==1)
{
dfs(nx,ny);
}
}
}
int main()
{
int ans=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='W'&&!vit[i][j])
{
dfs(i,j);
ans++;
}
}
}
cout<<ans;
}
优化
通常有5种方式：
- 最优化剪枝
- 可行性剪枝
- 排除等效冗余
- 记忆化
- 优化搜索顺序
其中1、2、4是较为常用的。
典例：
小木棍：
#include<bits/stdc++.h>
using namespace std;
int n,num[70],goal,cnt,sum,ans=0x3f3f3f3f;
bool vis[70];
inline bool dfs(int k,int len,int last)//last:最后失败
{
if(len==goal)
{
if(dfs(k+1,0,n))
{
return true;
}
}
if(k>=cnt) return true;
int cant=0;
for(register int i=last;i>=1;i--)//last前面都已经失败
{
if(!vis[i]&&len+num[i]<=goal&&cant!=num[i])
{
vis[i]=true;
if(dfs(k,len+num[i],i-1)) return true;//考虑不搜索i-1之前的区间(i-1是因为排序)
//因为循环能执行到i，是因为之前的木棍都已经失败或被用过，虽然不能保证last之后的都没有访问过，但也不用再考虑
vis[i]=false;
cant=num[i];//这个木棍失败
if(len==0||len+num[i]==goal) return false;
//len==0且失败时，说明当前方案不可能再拼接剩下的空木棍，不可能是答案
//len+num[i]==goal且失败时，说明当前用一根能拼好目标失败，那用别的方法不仅会占用更多的短木棍，也不能得到成功
}
}
return false;
}
int main()
{
cin>>n;
int l=0;
for(int i=1;i<=n;i++)
{
cin>>num[i];
if(num[i]>50)
{
n--;
continue;
}
l=max(l,num[i]);
sum+=num[i];
}
sort(num+1,num+1+n);//先拼大的，占空间
for(register int i=l;i<=sum;i++)
{
if(sum%i==0)
{
goal=i;
cnt=sum/i;
memset(vis,false,sizeof vis);
if(dfs(0,0,n))
{
cout<<i;
return 0;
}
}
}
cout<<sum;
return 0;
}
这道题需要同时使用剪枝123
关于“优化搜索顺序”：
这个比较少见。
#include<bits/stdc++.h>
using namespace std;
char mp[105][105];
int sx,sy,cnt,ans=0x3f3f3f,n;
int gox[4]={0,0,-1,1},goy[4]={-1,1,0,0};
int vis[105][105];
bool check(int x,int y)
{
if(x<1||x>n||y<1||y>n||cnt>=vis[x][y]||mp[x][y]=='x') return false;
else return true;
}
void dfs(int x,int y,int fx,bool fi)
{
if(mp[x][y]=='B')
{
ans=min(ans,cnt);
return;
}
if(cnt>=ans) return;
for(int i=0;i<4;i++)
{
int nx=x+gox[i],ny=y+goy[i];
if(check(nx,ny))
{
if(i!=fx&&!fi) cnt++;
vis[nx][ny]=cnt;
dfs(nx,ny,i,false);
if(i!=fx&&!fi) cnt--;
}
}
return;
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("p1-4.out","w",stdout);
cin>>n;
memset(vis,0x3f,sizeof(vis));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='A')
{
sx=i;
sy=j;
vis[i][j]=0;
}
}
}
dfs(sx,sy,0,true);
if(ans==0x3f3f3f) cout<<-1;
else cout<<ans;
}
如果修改dxdy数组顺序就不能AC（其实这个是有点巧的事情）
关于记忆化搜索：
是dp的一种实现方式。此处可见dfs与枚举其实有很大关系。
有一个简单例子：
求斐波那契数列的第k项
int fib(int n){
if(Ans[n]) return Ans[n];
if(n==1||n==2) return n;
Ans[n]=fib(n-1)+fib(n-2;
return Ans[n];
}
将算过的先存起来，避免重复计算
EOF
感谢观看。\(\huge QwQ\)
标签：return,int,dfs,vis,枚举,DFS,关于,bool From： https://www.cnblogs.com/haozexu/p/17488415.html