DFS提高——DFS常见模型
一、概述
DFS只能求出来是否能从起点到终点，不能求出来最短距离。
DFS一般代码比BFS要短一些因为不用维护队列，缺点是递归太深容易爆栈，栈空间应该是1MB左右
1、DFS——连通型
包括在BFS中见到的Flood Fill类型、图和树的遍历
一般题上是问能否从A点走到B点，或者从这个点出发能到达多少个符合要求的点
这类题一般是从棋盘上一个点到另一个点，每个点只需要走一遍，所以不需要恢复现场。
例题：1113. 红与黑 - AcWing题库
代码模板：
#include<iostream>
#include<cstring>
using namespace std;
const int N=25;
char g[N][N];
bool st[N][N];
int n,m,cnt=1,bex,bey,T;
int dx[4]={0,-1,0,1};//左上右下
int dy[4]={-1,0,1,0};
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(tx<0 || tx>=n || ty<0 || ty>=m)//出界
continue;
if(st[tx][ty] || g[tx][ty]=='#')//用过了或者不能走
continue;
st[tx][ty]=1;//标记
cnt++;//总数+1
dfs(tx,ty);//遍历下一个
}
return ;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int a,b;
while(cin>>m>>n,n||m)//n,m=0时结束
{
memset(st,0,sizeof st);//别忘了多组数据时要重置st的
cnt=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>g[i][j];
if(g[i][j]=='@')//记下终点坐标
{
bex=i;
bey=j;
}
}
}
st[bex][bey]=1;
dfs(bex,bey);
cout<<cnt<<endl;
}
return 0;
}
2、DFS——搜索顺序
搜索顺序类型的题，一般要考虑把所有顺序全部枚举到。
而且需要考虑恢复现场的问题，因为它是把当前棋盘看成一个整体，把棋盘当前的状态，转移成目标状态。
所以我们每次在搜索过程中，标记一个点往下DFS，回来的时候要把这个标记取消掉，方便这一层其他点进行DFS。
例题：1116. 马走日 - AcWing题库
代码模板：
#include<iostream>
#include<cstring>
using namespace std;
const int N=30;
int n,m,bx,by,T,res;
bool st[N][N];
int dx[8]={-1,-2,-2,-1,1,2,2,1};//从左上顺时针到左下
int dy[8]={-2,-1,1,2,-2,-1,1,2};
void dfs(int x,int y,int cnt)
{
if(cnt==n*m)//结束条件
{
res++;
return ;
}
for(int i=0;i<8;i++)//
{
int tx=x+dx[i];
int ty=y+dy[i];
if(tx<0 || tx>=n || ty<0 || ty>=m)//出界
continue;
if(st[tx][ty])//遍历过了
continue;
st[tx][ty]=1;//标记遍历过了
dfs(tx,ty,cnt+1);
st[tx][ty]=0;//恢复现场
}
return ;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
memset(st,0,sizeof st);//每次要重置st数组
res=0;
cin>>n>>m>>bx>>by;
st[bx][by]=1;//起点标记
dfs(bx,by,1);
cout<<res<<endl;
}
return 0;
}
3、DFS优化——剪枝与优化
常用5个方法：
1、优化搜索顺序
大部分情况下我们应该先搜分支较小的节点，一般通过对传入的数据先排个序
2、排除等效冗余
有些题在DFS并不需要考虑顺序，搜1 3 2 和搜1 2 3 是一个结果，一般我们用一个start变量记录当前搜到哪个点就行，下次从这个点往后，之前的不再搜索。
3、可行性剪枝
最常见的剪枝方式，如果不符合条件直接跳过
4、最优性剪枝
一般可以初始化一个变量记录当前最优解，如果递归时还没结束就已经超过了最优解，那么明显就不是答案，直接结束。
5、记忆化搜索（DP）
DP问题了，在这里不多讲
例题：167. 木棒 - AcWing题库
代码模板：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 70;
int n;
int w[N];//小木棍长度
int sum,length;//小木棍长度总和,当前每根木棍长度
bool st[N];//标记哪些小木棍用过了，1代表用过了
bool dfs(int u,int cur,int start)//u是大棍个数,cur是当前大棍长度,start记录从哪开始遍历
{
if(u*length==sum)//如果大棍个数*大棍长度=总和
return true;//成功
if(cur==length) //如果当前大棍的长度已经等于应该的长度,开一个新的大棍
return dfs(u+1,0,0);
for(int i=start;i<n;i++)//遍历小棍
{
if(st[i]||cur+w[i]>length) //如果当前小棍已经遍历过 或者 加上这个小棍大棍长度超了
continue;//跳过
st[i]=true;//标记小棍
if(dfs(u,cur+w[i],i+1))//递归
return true;
st[i]=false;//恢复现场
if(!cur||cur+w[i]==length)//如果当前大棍长度为0 或者加上小棍刚好为length
return false;//剪枝优化2,如果一个大棍的开头或者结尾失败,这层就失败
int j=i;
while(j<n&&w[j]==w[i])//剪枝优化3,如果当前小棍不行,和它长度相同的都不行
j ++ ;
i=j-1;
}
return false;
}
int main()
{
while(cin>>n,n)//读入,n==0时结束
{
memset(st,0,sizeof st);//每次重置状态数组
sum=0;//记录小棍总和
for(int i=0;i<n;i++)
{
cin>>w[i];//读入小棍长度
sum+=w[i];//计算总和
}
sort(w,w+n,greater<int>());//从大到小排序,搜索顺序的优化
length=1;//初始假设每根大棍长度应该为1,我觉得可以初始为最长的小棍长度.
while(true)//剪枝优化1,大棍长度一定是总长度的约数
{
if(sum%length==0 && dfs(0,0,0))//能整除而且可以让全部大棍长度为length
{
cout<<length<<endl;//就是最优解,因为length从小到大枚举
break;
}
length++;//如果不行长度+1
}
}
return 0;
}
4、DFS优化——迭代加深优化
一般是部分情况DFS会搜到很深的地方，但是答案在另一个很浅的分支里，
而迭代加深的思想，就是我每次规定一个最深搜索层数depth，如果每找到答案，就把depth++
如果有一个10层的树，
考虑一个一般情况，
如果答案在第3层（如下面图左上角的树），我们要是用迭代加深优化只用搜到第3层就结束了，如果是一般DFS我们会将第一个分支搜完，把第二个分支搜完，一直搜到第三个分支才能搜到答案
乍一看没差多少，但是由于DFS中每层的点按照指数级增长，每一个分支你搜到最深处会很费时间，只要我们“远远的看见是个死胡同”，就不用进去了，迭代就是让我们“远远的看”。
再看一个最坏情况，我们假设是一个满二叉树（除了最后一层每个点都有两个儿子）
如果有一个10层的树，答案就在在第10层，对于第10层我们要搜2^10，前九层加起来一共2^10-1，所以即使再最坏情况下，也不会低于正常DFS，而且这还是只有两个儿子，当儿子数更多时，迭代的效果会非常明显。
例题：170. 加成序列 - AcWing题库
代码模板：
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int n,p[N];//p记录路径
bool dfs(int u,int depth)//u为当前深度,depth为限制的最深深度
{
if(u==depth)//当当前深度已经到达限制
return p[u-1]==n;//判断当前最后一个数是否等于n
bool st[N]={0};//将st所有初始化为0,用来记录用过的数字
for(int i=u-1;i>=0;i--)//二重遍历,遍历u前所有可能的两个数的和
{
for(int j=i;j>=0;j--)
{
int tem=p[i]+p[j];
if(tem<=p[u-1] || st[tem] || tem>n)//如果和小于上一位 或 大于n 或 已经用过了
continue;//跳过
st[tem]=1;//标记
p[u]=tem;//记下路径,不用恢复现场的原因是后面会覆盖当前值
if(dfs(u+1,depth))//如果后面成功了
return true;
}
}
return false;
}
int main()
{
p[0]=1;//第一个点一定是1
while(cin>>n,n)
{
int depth=1;//深度为1,尽管每次会重复搜索,但把每层加起来的和也小于答案层的点的个数,当每个点分支越多时,就可以忽略掉
while(!dfs(1,depth))//当当前深度没有答案时,深度+1
depth++;
for(int i=0;i<depth;i++)//输出答案
printf("%d ",p[i]);
printf("\n");
}
return 0;
}
5、DFS优化——双向DFS
原理和双向BFS相类似，双向搜索可以减少中间指数级增长的搜索量。
例题：171. 送礼物 - AcWing题库
代码模板：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N=1<<24;
int n,m,k;//n是物品个数,m是最大重量,k是前半暴搜数量
int g[50],weights[N];//g是每个物品重量,weight是每种可能的和
int res,cnt;//res是答案,cnt是计数
void dfs(int u,int s)//u是当前遍历到的下标,s是当前的和,先暴搜前一半,打表
{
if(u==k)//当下标遍历完时
{
weights[cnt++]=s;//记录一下和
return ;
}
if((LL)s+g[u]<=m)//当 当前的和 与 当前下标对应的值 的和 小于最大重量
dfs(u+1,s+g[u]);//选择这个物品,继续递归
dfs(u+1,s);//不选这个物品
}
void dfs2(int u,int s)//u是当前遍历到的下标,s是当前的和,暴搜后一半
{
if(u==n)//当搜索到最后一个位置了,二分查找
{
int l=0,r=cnt-1;
while(l<r)
{
int mid=l+r+1>>1;
if(weights[mid]+(LL)s<=m)//当当前中间值+当前的和<=最大重量时
l=mid;
else
r=mid-1;
}
if(weights[l]+(LL)s<=m)//当找出来的大于等于差值的最小值符合条件
res=max(res,weights[l]+s);//更新最优解
return;
}
if((LL)s+g[u]<=m) //如果当前的和+当前下标对应的物品的重量没有超过限制
dfs2(u+1,s+g[u]);//选这个物品
dfs2(u+1,s);//不选这个物品
}
int main()
{
cin>>m>>n;
for(int i=0;i<n;i++)//读入物品重量
cin>>g[i];
sort(g,g+n,greater<int>());//从大到小排序,优化搜索顺序
k=n/2;// 不+2是为了防止 n = 1时，出现死循环
dfs(0,0);//对前半数据打表
sort(weights,weights+cnt);//把表从小到大排序方便二分
int t=1;//手动去重
for(int i=1;i<cnt;i++)
if(weights[i]!=weights[i-1])
weights[t++]=weights[i];
cnt=t;
dfs2(k,0);//从k开始
cout<<res<<endl;
return 0;
}
6、DFS优化——IDA*
一般来说配合迭代加深一起。思想上和A*算法差不多，都是找一个估计函数。
例题：180. 排书 - AcWing题库
代码模板：
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 15;
int n;
int q[N];
int w[5][N];
int f()//估计函数
{
int cnt=0;
for(int i=1;i<n-1;i++)
if(q[i]!=q[i-1]+1)//如果当前位的数字不是上一位数字+1
cnt++;//不符合顺序的个数+1
return (cnt+2)/3;//一次操作最多修正3个顺序,向上取整计算估计距离
}
bool check()//检查是否全部有序
{
for(int i=0;i<n-1;i++)
if(q[i+1]!=q[i]+1)
return false;
return true;
}
bool dfs(int depth,int max_depth)//depth是当前深度,max_depth是最大深度的限制
{
if(depth+f()>max_depth)//如果当前深度加上预估函数值大于最大深度,跳出
return false;
if(check())//如果当前满足题目要求,跳出
return true;
for(int len=1;len<=n;len++)//遍历长度
{
for(int l=0;l+len-1<n;l++)//遍历起点位置
{
int r=l+len-1;//r为端的末尾
for(int k=r+1;k<n;k++)//从r+1开始遍历所有点
{
memcpy(w[depth],q,sizeof q);//w暂存每层的状态,方便恢复现场
int x,y;//
for(x=r+1,y=l;x<=k;x++,y++)//x从r+1走到k,先把r+1~k之间的字母移动到前面位置
q[y]=w[depth][x];
for(x=l;x<=r;x++,y++)//再把l~r即要插入的字段放到上面字段的后面
q[y]=w[depth][x];
if(dfs(depth+1,max_depth))//如果递归得到了答案,就结束
return true;
memcpy(q,w[depth],sizeof q);//恢复现场,把之前的状态再恢复回来
}
}
}
return false;//递归全部还是没找到答案,失败
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=0;i<n;i++)
cin>>q[i];
int depth=0;
while(depth<5 && !dfs(0,depth))//迭代加深
depth++;
if(depth>=5)
puts("5 or more");
else
cout<<depth<<endl;
}
return 0;
}
