备战蓝桥杯Day11DFS

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; //这边不用写mark dfs(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-1 for(int i=1;i<=3;i++){ int j=(i+1<=3?i+1:1); //巧妙的解决3-1 for(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为和 //剪枝1 if(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; }