备战蓝桥杯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;
//这边不用写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;
}