备战蓝桥杯Day11 DFS

DFS

1.要点

(1)朴素dfs
下面保存现场和恢复现场就是回溯法的思想，用dfs实现，而本质是用递归实现，代码框架:

ans;                				//答案，常用全局变量表示 
int mark[N];                        //记录状态i是否被处理过
dfs(层数,其他参数){if(到达目的地，或者出局){		    //到达最底层，或者满足条件退出 更新答案 ans;      		//答案ans一般用全局变量表示 return ;           		//回溯，返回到上一层，在二叉树中是返回父节点 }//剪枝                  		    //进一步DFS之前剪枝，减少搜索范围 for(用i遍历下一层所有可能的情况)    //继续深入 if(mark[i]==0){				//如果状态i没有处理过，就可以进行下一层DFS mark[i]=1;				//标记状态i为已经使用，在后续的DFS时不能再使用 dfs(层数+1,其他参数);	    //下一层，继续深入DFS mark[i]=0; 			    //回复状态i，回溯时不影响上一层对这个状态的使用,难点 }return ;						//返回到上一层，可以返回一个结果 
}

第10行的mark[i]=1称为“保存现场”。第12行的mark[i]=0称为“恢复现场”。
适合每个状态都是唯一的，不存在重叠子问题，例如：N皇后问题、全排列问题、组合问题、图的遍历问题
(2)记忆化dfs
在朴素dfs的基础上新增了一个记录递归中间状态和数据的容器，难点在于状态数组要记录哪些状态，以及该状态下的什么值
适合存在重叠子问题，例如：斐波那契数列、爬楼梯问题、最长公共子序列、矩阵中的路径问题
(3)剪枝
优化回溯法，先暴力搜索，然后根据关系让搜索变少

2.题目

(1)朴素dfs

1508N皇后

学习:
(1)朴素dfs，考虑搜索深度就是行数，每一行放置皇后的状态是唯一的，不存在重叠子问题，不用记忆化，理解模版
代码:

#include <bits/stdc++.h>using namespace std;const int N=15;
int a[N][N],n,res; //a数组表示是否放置 bool check(int dep,int j){//先看看这一列行不行for(int i=1;i<=n;i++){if(a[i][j])	return false;}//再看左上方和右上方，因为按行搜索，所以下方不可能有 for(int i=dep,k=j;i>=1&&k>=1;i--,k--){ //中间条件用&& if(a[i][k])	return false;}for(int i=dep,k=j;i>=1&&k<=n;i--,k++){if(a[i][k])	return false;}return true;
}//按行数为深度一层层搜素 
void dfs(int dep){if(dep==n+1){ //n行搜索完 res++; //是一种情况 return; //回溯 }for(int j=1;j<=n;j++){ //遍历这一行放置在哪里 //能放置,则改变现场并向下搜索 if(check(dep,j)){a[dep][j]=1;//向下一行搜索dfs(dep+1);//恢复现场a[dep][j]=0;} 		 }
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;dfs(1);cout<<res;return 0;
}

2018小朋友崇拜圈

学习:
(1)dfs函数void和int没什么区别,void就是再递归结束条件里面更新ans，而int就是return ans
(2)与上一题不一样，直接dfs(1)，因为就是从第一行开始向下搜索，不断搜索，不断回溯，但是这个小朋友崇拜圈是每个小朋友都向下搜索并回溯一次，所有为dfs(i,0)
朴素dfs代码:

#include <bits/stdc++.h>using namespace std;const int N=1e5+10;
int n,a[N],ans;
int t,mark[N];//t为开始的小朋友id,mark数组表明该小朋友是否被遍历过 //当前第id个小朋友，以及之前遍历了cnt个小朋友 
void dfs(int id,int cnt){//递归结束条件 if(mark[id]){ //以及遍历过第id个小朋友，可能是圈，也可能不是圈 if(id==t){ //是圈 ans=max(ans,cnt);}return;}mark[id]=1;//第id个小朋友被访问，下面cnt+1 dfs(a[id],cnt+1);mark[id]=0;
}int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){t=i;//这边不用写markdfs(i,0);}cout<<ans;return 0;
}

(3)上面dfs存在一个圈每个小朋友都有搜索一次，有重复，利用时间戳优化，时间戳就是每个小朋友第几步被访问到并记录下来，利用之前记录的mindfn(最小时间戳)来判断是不是新的圈
![[小朋友崇拜圈.png]]
时间戳:1 3 2 4 5 6 8 7 9
有时间戳，说明访问过，例如从id=1开始，最小时间戳1，最终从id=5，时间戳为5，到id=3，时间戳为2>1，说明有新的圈，圈长度5-2+1=4.而从id=7,最小时间戳为8开始，到id=4,时间戳为4<8,说明访问之前时间戳的圈的元素，不算.
且在for循环内先判断时间戳是否存在，不存在在dfs，可以优化每个圈只访问1次
代码:

#include <bits/stdc++.h>using namespace std;const int N=1e5+10;
int n,a[N],ans;
int dfn[N],idx;//dfn为每个小朋友的时间戳，表示该小朋友是第几个被访问到的,idx记录当访问序号 
int mindfn;//记录当前时间戳，只有大于mindfn，才说明是新的圈，否则访问之前时间戳没用 //当前在第id个小朋友，返回圈的人数 
int dfs(int id){dfn[id]=idx++; //更新时间戳//递归出口if(dfn[a[id]]){ //有时间戳，说明访问到之前访问过的小朋友 if(dfn[a[id]]<mindfn)	return 0; //访问之前时间戳，不是个圈else	return dfn[id]-dfn[a[id]]+1; //访问mindfn之后的时间戳，是新的圈，注意不是减去dfnmin(因为可能不在圈中) }//没有时间戳就向下搜索,递归返回最终结果即可 return dfs(a[id]);}int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}idx=1; //从1开始 for(int i=1;i<=n;i++){ //遍历每个小朋友，寻找圈 if(!dfn[i]){ //该小朋友没被访问过，避免一个圈访问多次 mindfn=idx; //改变最小时间戳ans=max(ans,dfs(i)); }} cout<<ans;return 0;
}

(2)连通性

2023最大连通

学习:
(1)最简单常规的一道连通dfs，不过注意题目要求，最后输出答案即可，且输入的0和1是字符数组，不是整数数组(巨坑)!!!
代码:

#include <bits/stdc++.h>using namespace std;int const n=30,m=60;//加const才能编译通过
char a[n][m];//字符数组!!!
int mark[n][m],ans;
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};bool inmap(int x,int y){return 0<=x && x<n && 0<=y && y<m;
}int dfs(int x,int y){if(a[x][y]=='0')	return 0; //递归结束条件 mark[x][y]=1;int cnt=1;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(!inmap(nx,ny))	continue;if(a[nx][ny]=='1' && !mark[nx][ny])	cnt=cnt+dfs(nx,ny);}return cnt;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]=='1' && !mark[i][j]){ans=max(ans,dfs(i,j));}}}ans=148;cout<<ans;return 0;
}

连接草坪(II)

学习:
(1)这道题是dfs的应用，dfs就是给每块草坪(连通块)染上或标号，同时记录同一块草坪里面每个草地的位置坐标，为后续寻找最短路径做准备。
(2)寻找填补多少块土地能把所有连通块连起来，要分情况讨论，情况1是以某块土地到所有草坪路径和最少，情况2为草坪间距离和最少，所有最终答案就取最小的，但是情况1要减2，因为该块土地被计算2次，情况2也要减2，因为两块草坪的草地不算
(3)计算1-2,2-3,3-1时遍历，可以用j=(i+1<=3?i+1:1)来完美解决3-1问题
(4)vector的push_back换成emplace_back,其他容器的push也换成emplace，可以放进不用人为手动转换成符合类型元素
(5)最小值设置为1000，不要为1e4(double类型)，有些编译器会报错
代码:

#include <bits/stdc++.h>using namespace std;typedef pair<int,int> PII;
const int N=55;
char mp[N][N];
int n,m,ans;
int mark[N][N],cid; //给同一块草坪染上同一个颜色,等同于标号 
vector<PII> v[4]; //记录同一颜色草坪的位置坐标 
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};bool inmap(int x,int y){return 0<=x && x<n && 0<=y && y<m;
}void dfs(int x,int y,int c){ //dfs给同一块草坪染上颜色c if(mp[x][y]=='.')	return; //递归出口mark[x][y]=c;v[c].emplace_back(x,y); //push_back(make_pair(x,y))要清楚知道存入什么类型，而emplace_back系统判断 for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(!inmap(nx,ny))	continue;if(mp[nx][ny]=='X' && !mark[nx][ny])	dfs(nx,ny,c);} 
}//位置x,y到草坪c的最小曼哈顿距离 
int count(int x,int y,int c){int minn=1e4;for(auto a:v[c]){minn=min(minn,abs(x-a.first)+abs(y-a.second));}return minn;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>mp[i][j];}}//先dfs染色 cid=1;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mp[i][j]=='X' && !mark[i][j]){dfs(i,j,cid);cid++;}}}ans=1000; //枚举每块地，寻找土地到3块草坪的最短路径和for(int i=0;i<n;i++){for(int j=0;j<m;j++){		if(mp[i][j]=='.'){int cnt=0;for(int k=1;k<=3;k++){cnt+=count(i,j,k);} //3块草坪，最终答案多算了2次土地(i,j) ans=min(ans,cnt-2);}}} //再看草坪到草坪的距离int minn[]={0,1000,1000,1000};//1-2,2-3,3-1for(int i=1;i<=3;i++){int j=(i+1<=3?i+1:1); //巧妙的解决3-1for(auto a:v[i]){minn[i]=min(minn[i],count(a.first,a.second,j));} } for(int i=1;i<=3;i++){ans=min(ans,minn[i]+minn[(i+1<=3?i+1:1)]-2); //这里的减2是减去2块草地，答案只要土地数量 }cout<<ans;return 0;
}

2018全球变暖

学习:
(1)连通块问题，需要开个地图数组以及mark数组记录联通块中每一块是否访问过，保证每个联通块只搜索一次，dfs是void可以没有最终递归条件然后return，函数目的就是更新状态，更新mark数组以及判断该联通块是否会被淹没，更新tag(本质是类似于更新ans)
代码;

#include <bits/stdc++.h>using namespace std;const int N=1e3+10;
char mp[N][N];
int n,ans,mark[N][N],tag;
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};void dfs(int x,int y){mark[x][y]=1; //标记访问过//题目说照片保证第1行、第1列、第N行、第N列的像素都是海洋，不用判断是否会越界，否则正常要判断 if(mp[x][y-1]=='#' && mp[x][y+1]=='#' && mp[x-1][y]=='#' && mp[x+1][y]=='#'){tag=0; //存在一个不会被淹没的陆地，该岛屿不会被完全淹没 } //继续dfs，目的是标记联通块和判断是否会被淹没for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];//同上，不用判断地图越界if(mp[nx][ny]=='#' && !mark[nx][ny])	dfs(nx,ny); //是陆地且未访问过继续搜索 } 
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>mp[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){tag=1; //tag标记是否会被完全淹没 if(mp[i][j]=='#' && !mark[i][j]){ //是陆地且未被访问过才搜索，保证一个联通块岛屿只搜素一次 dfs(i,j);if(tag)	ans++; //被完全淹没岛屿加1 }}}cout<<ans;return 0;
}

(3)记忆化

3820混境之地5

学习:
为矩阵中的路径问题，可以记忆化dfs
(1)地图搜索，一般从1开始，构造个方向数组，遍历四个方向即可,再写个判断函数是否不在地图，得到新位置优先判断是否在地图中

int dx[]={0,0,-1,1},dy[]={-1,1,0,0}; //方向数组，学习for(int i=0;i<4;i++){  //开始四个方向搜索 int nx=x+dx[i],ny=y+dy[i];    //x,y为传入的当前位置,nx，ny为目标位置if(!inmap[nx][ny])	continue; //先判断目标搜索位置在不在地图里面，不在直接换方向 

代码:
(1)暴力DFS，没有记忆化记录，四个方向都深入到底，这题也能得满分

#include <bits/stdc++.h>using namespace std;
const int N=1e3+10;
int n,m,k,sx,sy,ex,ey,h[N][N]; //sx,sy为开始位置,ex,ey为出口,h数组记录高度
int dx[]={0,0,-1,1},dy[]={-1,1,0,0}; //方向数组，学习bool inmap(int x,int y){  //是否在地图中return 1<=x && x<=n && 1<=y && y<=m;
}bool dfs(int x,int y,int t){ //当前位置和使用喷漆背包次数 if(x==ex && y==ey)	return true; //先写最终情况for(int i=0;i<4;i++){  //开始四个方向搜索 int nx=x+dx[i],ny=y+dy[i];if(!inmap(nx,ny))	continue; //先判断目标搜索位置在不在地图里面，不在直接换方向 //没用过喷漆背包 if(t==0){//使用喷漆背包,说明当前位置高度+喷漆背包能提升高度>=目标位置高度，没有记忆化记录数组就是再判断dfs(nx,ny,t+1) if(h[x][y]+k>=h[nx][ny] && dfs(nx,ny,t+1)){return true;}//不用喷漆背包else if(h[x][y]>h[nx][ny] && dfs(nx,ny,t)){return true;}}//用过喷漆背包，不能使用else{if(h[x][y]>h[nx][ny] && dfs(nx,ny,t)){return true;}}	 } //在当前位置四个方向都无法前进且当前位置不在终点，说明不能到达return false; 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>k>>sx>>sy>>ex>>ey;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>h[i][j];}}cout<<(dfs(sx,sy,0)?"Yes":"No");return 0;
}

(2)使用记忆化数组dp[x][y][t],(不是bool,而是int,因为要赋初值-1判断)表示在x，y位置，背包使用次数t这一状态下是否搜索过该位置且该位置是否能继续搜索下去.初始值-1,表示没有搜索过，若为0，表示搜索过，但无法再往四个方向更深层次搜索，若为1，表示搜索过，且可以往更深层次搜索

int dp[N][N][2]; //记忆化搜索数组 //main中memset初始化
memset(dp,-1,sizeof(dp));//dfs中对dp数组赋值
bool dfs(int x,int y,int t){ //当前位置和使用喷漆背包次数 if(x==ex && y==ey)	return true; //先写最终情况if(dp[x][y][t]!=-1)	return dp[x][y][t]; //搜索过不再搜索 for(int i=0;i<4;i++){  //开始四个方向搜索 int nx=x+dx[i],ny=y+dy[i];if(!inmap(nx,ny))	continue; //先判断目标搜索位置在不在地图里面，不在直接换方向 //没用过喷漆背包 if(t==0){//使用喷漆背包,说明当前位置高度+喷漆背包能提升高度>=目标位置高度 if(h[x][y]+k>=h[nx][ny] && dfs(nx,ny,t+1)){dp[x][y][t]=true; //记忆化 return true;}//不用喷漆背包else if(h[x][y]>h[nx][ny] && dfs(nx,ny,t)){dp[x][y][t]=true; //记忆化 return true;}}//用过喷漆背包，不使用else{if(h[x][y]>h[nx][ny] && dfs(nx,ny,t)){dp[x][y][t]=true; //记忆化 return true;}}	 } //在当前位置四个方向都无法前进且当前位置不在终点，说明不能到达dp[x][y][t]=false;//记忆化 return false; 
}

2014地宫取宝

要点:
矩阵中的路径问题，可以记忆化dfs
(1)记忆化想好dp数组记录哪些状态，记录的又是什么值，dp数组记录的状态就是dfs函数的参数

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N=55,p=1e9+7;  
int n,m,k,v[N][N];//v为地图宝贝价值 
ll dp[N][N][15][15]; //dp为状态数组，表示在(x,y)位置，宝贝最大值为maxn,宝贝数量为t件这一状态的方案个数 
int dx[]={0,1},dy[]={1,0};bool inmap(int x,int y){return 1<=x && x<=n && 1<=y && y<=m;
}//状态为位置(x,y),当前宝贝最大值maxn,宝贝数量cnt 
ll dfs(int x,int y,int maxn,int cnt){  if(x==n && y==m)	return cnt==k; //最终条件，判断cnt等不等于k，等于才方案数加1 if(dp[x][y][maxn][cnt]!=-1)	return dp[x][y][maxn][cnt]; //搜索过了，直接返回方案个数 ll res=0; //从当前位置开始的方案个数for(int i=0;i<2;i++){int nx=x+dx[i],ny=y+dy[i];if(!inmap(nx,ny))	continue;//拿宝贝,说明此地宝贝价值大于当前宝贝最大值且宝贝数量小于k if(v[nx][ny]>maxn && cnt<k){res=(res+dfs(nx,ny,v[nx][ny],cnt+1))%p; //要去余记得每个地方都要取余 }//不拿宝贝 ,说明此地宝贝价值小于当前宝贝最大值或者宝贝数量大于等于k //不能写else,否则对于当前位置，遗漏了以拿但选择不拿的情况，但实际上后面可能有更好的，每个位置都可以不拿宝贝 res=(res+dfs(nx,ny,maxn,cnt))%p; }	return dp[x][y][maxn][cnt]=res; //记忆化更新 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);memset(dp,-1,sizeof(dp));cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>v[i][j];v[i][j]++;//状态数组宝贝最大值初值为0，不好变为-1，所以把价值整体+1，避免0,不影响方案个数 }}cout<<(dfs(1,1,0,0)+dfs(1,1,v[1][1],1))%p;//在(1,1)两种情况，拿或不拿，两种情况独立相加 return 0;
} 

(4)剪枝

数字王国之军训排队

学习：
(1)用一个mark数组来标记该序号的学生是否已经被划分为之前的队伍中，是的话直接dfs下一层，就是剪枝
(2)注意vector<int> v[N]表示一个大小为N的数组v，里面元素类型为vector<int>,等同于vector<vector<int>> v,但是用vector<int> v[N]更好操作
代码；

#include <bits/stdc++.h>using namespace std;const int N=15;
int a[N],n,ans,mark[N];
vector<int> v[N];//记录每一队里面学生名字，注意这个v数组里面元素类型是vector<int>，v数组大小为N void dfs(int x){//递归出口 if(x==n)	return;//剪枝，如果已经在队伍中，直接跳过 if(mark[x])	dfs(x+1);bool t=true;for(auto &i:v[ans]){ //v[ans]为vector<int>,遍历vector<int> if(a[x]%i==0 || i%a[x]==0){t=false;break;}}if(t){mark[x]=1;v[ans].emplace_back(a[x]);}dfs(x+1);
}int main(){ios::sync_with_stdio(false);cin>>n;for(int i=0;i<n;i++)	cin>>a[i];for(int i=0;i<n;i++){if(!mark[i]){dfs(i);ans++;}}cout<<ans;return 0;
}

特殊的多边形

学习:
(1)n边型n条边的排列选择就是dfs递归的层数，通过计算每一条边的上限来进行剪枝，最后利用一下前缀和,不过三角形可以3层暴力枚举，不过枚举范围要开大点
代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N=1e5+10;
int t,n;
ll a[N],prefix[N];void dfs(int dep,int st,int mul,int sum){ //dep为层数，就是n边形的边数，st为前一条边长度，mul为乘积，sum为和 //剪枝1if(mul>N)	return; 	//递归出口 if(dep==n+1){a[mul]++;return;}//剪枝2，获取此边上限长度，mul*x^(n-dep+1)<=N,再移项可得,x<=(N/mul)^(1/(n-dep+1)) int up=pow(1.0*N/mul,1.0/(n-dep+1))+3; //得加个数后面，下面为小于up，不然可能最后的值取不到//剪枝3，最后一条边考虑sum，类似于三角形两边之和大于第三边,其余的考虑up for(int i=st+1;i<(dep==n?sum:up);i++){ dfs(dep+1,i,mul*i,sum+i);}
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>t>>n;dfs(1,0,1,0); //从第一层开始，乘积从1开始 for(int i=1;i<=N;i++){prefix[i]=prefix[i-1]+a[i];}for(int i=0;i<t;i++){int l,r;cin>>l>>r;cout<<prefix[r]-prefix[l-1]<<endl;}return 0;
}

数的划分

学习:
(1)跟上面剪枝一样，只不过上面是乘积，这里是和,注意st从1开始
代码:

#include <bits/stdc++.h>using namespace std;int n,k,ans;void dfs(int dep,int st,int sum){ //层数，前一个数，和 if(sum>n)	return;if(dep==k+1 && sum<n)	return;if(dep==k+1 && sum==n){ans++;return;}//剪枝1，求上限,sum+x*(k-dep+1)<=n,即x<=(n-sum)/(k-dep+1) int up=1.0*(n-sum)/(k-dep+1)+1;for(int i=st;i<up;i++){dfs(dep+1,i,sum+i);} 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;dfs(1,1,0);cout<<ans;return 0;
}