蓝桥杯备赛日记——DFS基础

1.DFS剪枝

OJ2942 数字王国之军训排队

思路

写一个dfs函数，这个dfs函数有两个参数，dep和i，dep表示第dep位同学，i表示打算把所有人分成i支队伍，这个函数的功能是来检测是否能把所有同学分成i支队伍，更加严谨的来说是检测能否把第dep位同学分到这i支队伍里面的某支队伍里面，如果能分，(先把它塞进能分进去的那支队伍里面(用vector数据结构))，那就看看下一位同学也就是第dep+1位同学能不能分到这i支队伍里面的某支队伍里面，如果此时dep==n+1就说明全部为同学是能够分为i支队伍的。

代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//思路：dfs，这题的dfs函数的作用是试一试所有同学分成i队能不能成功，如果成功返回true
//重要的数据结构vector
const int N=11;
int n;
int a[N];
vector<int> v[N];//对vector数据结构了解还是比较浅，记得好好学习一下
bool dfs(int dep,int i)//dfs(dep,i)表示分配到第dep位同学能否分成i队
{if(dep==n+1)return true;//达到n+1层就说明可以分成i队，返回true，表示能成for(int j=1;j<=i;j++)//分别枚举分成的i只队伍里面各自队伍里所有的成员{bool flag=true;//先假设他能留在第j支队伍里面for(const auto &x:v[j])//枚举第j支队伍里面的所有成员{if(a[dep]%x==0||x%a[dep]==0)//看看能不能被整除{flag=false;//如果能被整除说明第dep个同学不能留在第j支队伍里面break;}}if(flag==false)continue;//如果不能留在第j支队伍里面，看看下一支队伍能不能v[j].push_back(a[dep]);//如果能那就把第dep位同学放在第j支队伍里面if(dfs(dep+1,i))return true;//递归下一层v[j].pop_back();//恢复现场}return false;
}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){if(dfs(1,i))//如果能分成i队，那就输出i，跳出循环，这就是最少的队伍数量{cout<<i;break;}}return 0;
}

OJ1508 N皇后

思路

开一个数组vi[i][j]，如果坐标[i][j]的vi[i][j]大于零就说明有皇后占用了。
写一个dfs函数，去搜索每一行的哪一列可以放置皇后，在一个位置放置完皇后后，的把他所在位置的米字型方向位置都用vi[i][j]++，表示位置已经被占用，然后去搜下一层(dfs(dep+1))，然后恢复现场vi[i][j]–；

代码

#include <iostream>using namespace std;
const int N=12;int vi[N][N];
int n,ans=0;
void dfs(int dep)//dep表示行
{//跳出条件if(dep==n+1)//如果递归搜索到n+1层就说明当前方案是一种可行方案{ans++;//方案数加加return;//当前递归结束}for(int i=1;i<=n;i++)//枚举列{if(vi[dep][i])continue;//如果但前dep行i列有人占用的话就跳过//改变状态//当前[dep][i]所在的米字型都vi++for(int _j=1;_j<=n;_j++)vi[dep][_j]++;//当前dep行所有列都被占用了for(int _i=1;_i<=n;_i++)vi[_i][i]++;//当前位置一列都被占用了for(int _i=dep,_j=i;_i>=1&&_j>=1;_j--,_i--)vi[_i][_j]++;//米字型左上角for(int _i=dep,_j=i;_i>=1&&_j<=n;_j++,_i--)vi[_i][_j]++;//米字型右上角for(int _i=dep,_j=i;_i<=n&&_j>=1;_j--,_i++)vi[_i][_j]++;//米字型左下角for(int _i=dep,_j=i;_i<=n&&_j<=n;_j++,_i++)vi[_i][_j]++;//米字型右下角dfs(dep+1);//递归搜索下一层
//恢复现场for(int _j=1;_j<=n;_j++)vi[dep][_j]--;//当前dep行所有列都被占用了for(int _i=1;_i<=n;_i++)vi[_i][i]--;//当前位置一列都被占用了for(int _i=dep,_j=i;_i>=1&&_j>=1;_j--,_i--)vi[_i][_j]--;//米字型左上角for(int _i=dep,_j=i;_i>=1&&_j<=n;_j++,_i--)vi[_i][_j]--;//米字型右上角for(int _i=dep,_j=i;_i<=n&&_j>=1;_j--,_i++)vi[_i][_j]--;//米字型左下角for(int _i=dep,_j=i;_i<=n&&_j<=n;_j++,_i++)vi[_i][_j]--;//米字型右下角}}
int main()
{cin>>n;dfs(1);//求结果cout<<ans;return 0;
}

OJ182小朋友崇拜圈

思路

用时间戳数组dfn[N]去记录每一个小朋友是第几个走到的,mindfn用来表示进入一个圆圈前走到的第一个点的时间戳。
写一个dfs函数，这个函数的参数是x，x表示当前走到的同学编号，走当前的x同学的时候，就给他记录一个时间戳，在判断它崇拜的同学之前是否走过，如果走过，那么可能会构成一个圆圈，在判断它崇拜的同学的时间戳是否小于等于进入这个圆圈时走过的第一个点的时间戳，如果符合那确实构成了一个圆圈，那就返回圆圈长度(dfn[x]-dfn[a[x]]+1),如果它崇拜的同学的时间戳不满足这个条件，那就说明构成不了一个圆圈，那就返回0；
如果连一开始的判断都不符合(当前x同学崇拜的同学没有被走过)，那就继续去当前x同学崇拜的同学搜下去。

代码

#include <iostream>using namespace std;const int N=1e5+9;
int mindfn,dfn[N],a[N];//mindfn表示进入一个圆圈前第一个点的时间戳//dfn[i]表示第i个点时间戳
//a[i]表示第i个同学崇拜的同学的编号
int indx;//时间戳,最后时间戳会等于n
int ans=0;
int dfs(int x)
{dfn[x]=++indx;if(dfn[a[x]])//如果第x个同学崇拜的同学之前已经走过，那就说明可能会构成一个圆圈{//如果如果第x个同学崇拜的同学的时间戳大于等于进入这个元之前第一个点的时间戳，那就说明//能构成一个圆圈，那就返回一个圆圈的长度if(dfn[a[x]]>=mindfn)return dfn[x]-dfn[a[x]]+1;//返回圆圈长度return 0;//如果没有构成圆圈，那圆圈长度就是为0}return dfs(a[x]);//如果第x个同学崇拜的同学之前没有走过，那就从第x个同学崇拜的同学继续走下去}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){if(!dfn[i]){mindfn=indx+1;//进入一个新的圆圈时间戳当然要+1了，不然用上一个圆圈最后一个数的的时间戳吗？ans=max(ans,dfs(i));//更新最大圆圈的人数}}cout<<ans<<endl;return 0;
}

OJ178全球变暖

思路

先用dfs将不同的岛屿染上不同的颜色，然后计算最后剩下的岛屿的颜色有多少种，用原先总岛屿数(即颜色数)减去剩余颜色数，得到的就是淹没的岛屿数量需要考虑的细节较多，自己多加理解

代码

#include <iostream>using namespace std;
const int N=1e3+9;
char mp[N][N];
int scc;//表示颜色编号
int col[N][N];//表示某个位置的颜色
bool vi[N*N];//表示当前颜色之前是否出现过int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
//dfs函数就是给每一个岛屿里的陆地染色void dfs(int x,int y)//把点[x][y]所在的岛屿里面所有的陆地都染成相同的颜色
{col[x][y]=scc;//染色for(int k=0;k<4;k++)//搜索周围四个方向{int nx=x+dx[k];int ny=y+dy[k];if(col[nx][ny]||mp[nx][ny]=='.')//如果当前点周围的点被染过色或者是海洋，那就跳过{//没有col[nx][ny]会反复横跳continue;}dfs(nx,ny);//从周围是陆地的点继续向下搜陆地}
}int main()
{int n;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++){//如果当前点已经染过色了或者当前点是海洋，那就跳过if(col[i][j]||mp[i][j]=='.')continue;scc++;//否则那就是没染过颜色的陆地了，那颜色编号就得++了dfs(i,j);//给当前陆地所在的岛屿里面所有的陆地都染成一种颜色}}//遍历每一个点，看看哪一个点是不可淹没点，并且看看这个不可淹没点的颜色有没有出现过
//把不可淹没点的颜色计数
int ans=0;//不可淹没点的颜色种数(淹没后剩余的岛屿数量)for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j]=='.')continue;//如果当前点是海洋那就跳过bool flag=true;//如果不是海洋，那就先假设当前这个块陆地是不可淹没点for(int k=0;k<4;k++)//看看他周围四个点是不是全是陆地{int nx=i+dx[k];int ny=j+dy[k];if(mp[nx][ny]=='.'){flag=false;break;}}if(flag)//如果确实全部都是陆地，那当前这个点就是不可淹没点{if(!vi[col[i][j]])//那就再判断当前这个不可淹没点之前染的颜色在之前有没有出现过{ans++;//如果没有出现过，那剩余颜色数量(剩余岛屿数量)++vi[col[i][j]]=true;//改变状态，表示当前岛屿的颜色已经出现过了}}}}cout<<scc-ans;//所有颜色-剩下的颜色=没有被淹没之前所有岛屿的数量-淹没后剩余的岛屿数量=被淹没的岛屿数量return 0;
}

OJ3075 特殊的多边形

思路

不妨规定我们构造出的n元组是递增的，那么在搜索过程中我们就可以通过计算得到当前这个位置的上限(剪枝的关键)dfs过程中记录乘积，因为乘得越多数字越大，当乘积mul>le5时直接返回(乘积很容易就超过1e5)同时还能记录一下n-1条边的长度和sum，最后一条边必须小于sum.
最后用前缀和快速进行区间查询:

代码

#include <iostream>
#include <cmath>
using namespace std;int t,n;const int N=1e5+9;
int ans[N],pre[N];
//dfs(dep,st,mut,sum)表示开始选择第dep个数，上一个数字也就是第dep-1个数字选的是st
//选完上一个数之后的乘积为mut，所有的数字和为sum
void dfs(int dep,int st,int mut,int sum)
{if(mut>1e5)return;//剪枝1//递归出口if(dep==n+1)//搜到这一层，说明当前选的所有数字都符合条件{ans[mut]++;//满足每条边的乘积为mutde的多边形数量++return;}
//假设是5边形，mut*x*y*z<=1e5; 那x的上界不就是pow(1e5/mut,1.0/(5-(3-1)))+10int up=pow(1e5/mut,1.0/(n-(dep-1)))+10;//剪枝2，确定第dep个数字的上界//在这里的循环范围条件是如果到选择(枚举)最后一条鞭的时候，要考虑任意两边之和大于第三边
//因为已经是让n条边数值单调递增的，比如三角形，a<b<c,你只要在选择最后一条鞭的时候判断
//第三条边c是否小于sum=a+b
//有的人可能会疑问，为什么不确定a+c是否大于b或者b+c是否大于a，
//因为他们是单调递增的，所有一定会有这个性质
//其他多边形也有这个性质for(int i=st+1;i<(dep==n ? min(sum,up):up);i++){dfs(dep+1,i,mut*i,sum+i);//去搜索下一层合适的数}
}
int main()
{cin>>t>>n;dfs(1,0,1,0);//最开始肯定是从第一个数字开始选，所以dep=1，上一个选的数为0，一位上一个数字选不了啊//乘积肯定为1，因为1乘与任何数字都是1，和为0，因为还没有选数字啊，所有sum为0for(int i=1;i<=1e5+9;i++){pre[i]=pre[i-1]+ans[i];//对ans数组做前缀和，方便求区间和}while(t--){int l,r;cin>>l>>r;cout<<pre[r]-pre[l-1]<<endl;}return 0;
}

OJ3935 仙境诅咒

代码

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=1e3+9;
struct node
{int x,y;bool s=false;
}a[N];
int D,n;
int getd(int x1,int y1,int x2,int y2)//计算两点之间的公式
{return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}void dfs(int x,int y)//从已诅咒者向其他修仙者扩散，看看谁和这个已诅咒者距离满足诅咒条件
{for(int i=1;i<=n;i++){if(a[i].s)continue;//如果已经被诅咒了，那就跳过，否则会反复横跳，和染色题里的岛屿里面的陆地一样if(D*D>getd(x,y,a[i].x,a[i].y))//如果没有被诅咒那就看看是否满足诅咒条件{a[i].s=true;//如果，满足那就变为true，表示已经被诅咒dfs(a[i].x,a[i].y);//从这个被诅咒者向下搜}}
}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;cin>>D;a[1].s=true;dfs(a[1].x,a[1].y);for(int i=1;i<=n;i++){if(a[i].s){cout<<1<<endl;}else {cout<<0<<endl;}}return 0;
}

OJ4234

思路

思路和OJ178全球变暖题目思路一样，就是染色，把同一个大水洼里面的各个小水洼染成同一个颜色，最后对相同颜色的小水洼里面的水量去累加求和。

代码

#include <iostream>
using namespace std;
//思路：染色，同一个大水洼里的小水洼都染成一个颜色，和OJ178全球变暖题目岛屿陆地染色一样
const int N=1e2+9;
int mp[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n,m;
int scc;
int col[N][N];
long long v[N*N];//注意开long longvoid dfs(int x,int y)
{col[x][y]=scc;//染色for(int k=0;k<4;k++){int nx=x+dx[k];int ny=y+dy[k];if(col[nx][ny]||mp[nx][ny]==0)continue;//如果当前水洼已经被染色了或者水洼里的水为0，那就跳过dfs(nx,ny);//向附近的水洼继续搜索}
}int main()
{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]==0||col[i][j])如果当前水洼已经被染色了，那就跳过防止重复染色//或者水洼里的水为0，也跳过，我们只给水洼里水量不为0的水洼染色{continue;}scc++;//颜色标号++dfs(i,j);//染色}}long long ans=0;//注意开long longfor(int i=1;i<=n;i++){for(int j=1;j<=m;j++)//把相同颜色的小水洼里面的水量都相加，就是大水哇的总水量{if(col[i][j])//如果当前水洼染了色{v[col[i][j]]+=mp[i][j];//把同一个颜色里的小水洼里面的水量相加ans=max(v[col[i][j]],ans);//更新最大大水洼里面的水量}}}cout<<ans;return 0;
}

OJ4360 串变换

思路

先写一个chang_s用于去执行题目中给的两种操作，这个函数有个change_status参数，如果为真就是正向进行，如果是false逆向进行，用于恢复现场；还要建立一个bool 型的数组vi[N]用于判断某个方案是否用过；
写一个bool 型dfs函数，这个函数的参数就是dep，如果搜索过程中depk+1，就说明这种方案不行，搜到了第k+1层都还没返回true，这是dfs跳出的第二个条件，在这个条件之前的跳出条件是if(st)return true；搜索开始之前先判断改变玩的s和t是否相等。这两个条件之后就是遍历每一种操作，如果在某一条dfs中当前遍历到的操作已经使用过了，那就跳过，否则就先去正向执行chang_s函数，并标记vi数组为真，然后去搜索该条数的下一层，if(dfs(dep+1))return true;如果下一层能成就返回true，如果下一层不能成，那就恢复现场；

代码

#include <iostream>using namespace std;
int n,k;
string s,t;
bool vi[8];
struct{int key;int x;int y;
}a[8];void change_s(int i,bool change_status)//change_status如果是true就是只正操作，否则相反
{if(a[i].key==1){int temp=s[a[i].x]-'0';if(change_status==true){temp=(temp+a[i].y)%10;}else{temp=(temp+10-a[i].y)%10;}s[a[i].x]=temp+'0';}else{swap(s[a[i].x],s[a[i].y]);}
}bool dfs(int dep)
{if(s==t)return true;//跳出条件if(dep==k+1)return false;//跳出条件for(int i=1;i<=k;i++)//遍历每一种操作{if(vi[i])continue;//如果当前操作已经被采用过了，那跳过去下一种看看vi[i]=true;//表示该种操作已经用了change_s(i,true);//进行操作if(dfs(dep+1))return true;//去下一层继续搜索，如果能成就返回true//恢复现场vi[i]=false;change_s(i,false);//逆操作恢复现场}return false;//怕前面7种方案否分别作为第一种方案去搜索都不能成，这里要写返回false。
}int main()
{cin>>n>>s>>t>>k;for(int i=1;i<=k;i++)cin>>a[i].key>>a[i].x>>a[i].y;cout<<(dfs(1) ? "Yes":"No");return 0;
}

OJ4494 黄金树

代码

#include <iostream>using namespace std;const int N=1e5+9;
int sz[N][2];
int w[N];
int sum=0;void dfs(int x,int key)//表示当前x点的黄金指数为key
{if(key==0)sum+=w[x];//如果当前x点的黄金指数为0，那就累加他的权重//去他的子节点继续搜索if(sz[x][0]!=-1)dfs(sz[x][0],key+1);if(sz[x][1]!=-1)dfs(sz[x][1],key-1);
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>w[i];for(int i=1;i<=n;i++){cin>>sz[i][0]>>sz[i][1];}dfs(1,0);cout<<sum;return 0;
}

OJ3817 混境之地

代码

#include <iostream>
using namespace std;const int N=1e3+9;
char mp[N][N];
char col[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int scc=0;
void dfs(int x,int y,char s)
{col[x][y]=s;for(int k=0;k<4;k++){int nx=x+dx[k];int ny=y+dy[k];if(col[nx][ny]==s||mp[nx][ny]!='.')continue;dfs(nx,ny,s);}
}
int main()
{int n,m;cin>>n>>m;int a,b,c,d;cin>>a>>b>>c>>d;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>mp[i][j];}}int l,h;dfs(a,b,'@');if(col[a][b]==col[c][d]){cout<<"Yes";return 0;}else{dfs(c,d,'*');for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(mp[i][j]=='#'){for(int k=0;k<4;k++){int nx=i+dx[k];int ny=j+dy[k];if(col[nx][ny]=='@')l==1;if(col[nx][ny]=='*')h==1;}if(l&&h){cout<<"Yes";return 0;}}}}cout<<"No";}return 0;
}

OJ216 地宫取宝

代码

#include <iostream>
#include <cstring>using namespace std;int n,m,k;
int c[55][55];
int dx[]={1,0};
int dy[]={0,1};
long long p=1e9+7;bool check(int x,int y)
{return x>=1&&x<=n&&y>=1&&y<=m;
}long long dp[55][55][15][15];
long long dfs(int x,int y,int cnt,int mx)//表示到(x,y)点开始，已经哪了cnt件宝贝，手里宝贝的最大价值是mx
{if(dp[x][y][cnt][mx]!=-1)return dp[x][y][cnt][mx];//记忆化if(x==n&&y==m)return cnt==k;//如果搜索到坐标为终点，再判断cnt是不是等于k，如果等于k那就是一种方案//返回true，也就是1，否则返回false 0；long long res=0;//方案数for(int i=0;i<2;i++){int nx=x+dx[i];int ny=y+dy[i];if(!check(nx,ny))continue;//防止坐标越界//选择拿if(c[nx][ny]>mx&&cnt<k)res=(res+dfs(nx,ny,cnt+1,c[nx][ny]))%p;//累加选择拿的方案数//选择不拿res=(res+dfs(nx,ny,cnt,mx))%p;//累加选择不拿的方案数}return dp[x][y][cnt][mx]=res;//方案数
}int main()
{memset(dp,-1,sizeof(dp));cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c[i][j];c[i][j]++;//注意审题，价值可以为0，为防止（1，1）位置的宝物价值为0，我们把所有位置的宝物价值都+1//防止dfs(1,1,0,0)和dfs(1,1,1,c[1][1])一个意思，不知道第一个宝物拿没拿}}cout<<(dfs(1,1,0,0)+dfs(1,1,1,c[1][1]))%p;return 0;
}

OJ3820 混境之地5

代码

#include <iostream>
using namespace std;int n,m,k;
int sx,sy,fx,fy;
const int N=1e3+9;
int h[N][N];int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};bool check(int x,int y)//检查是否越界
{return x>=1&&x<=n&&y>=1&&y<=m;
}bool dp[N][N][2];
bool dfs(int x,int y,int t)//(x,y)表示从这个点开始搜索，t表示是否用过了能力背包，t==0表示没有背包，
//t==1表示用了背包
{if(dp[x][y][t])return dp[x][y][t];if(x==fx&&y==fy)return dp[x][y][t]=true;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(!check(x,y))continue;//如果坐标越界跳过//如果之前没有用喷气背包if(t==0){//选择用if(h[x][y]+k>h[nx][ny]&&h[x][y]<h[nx][ny]&&dfs(nx,ny,1))return dp[nx][ny][1]=true;//选择不用if(h[x][y]>h[nx][ny]&&dfs(nx,ny,0))return dp[nx][ny][0]=true;}else{//如果之前用过背包if(h[x][y]>h[nx][ny]&&dfs(nx,ny,1))return dp[nx][ny][1]=true;}}return dp[x][y][t]=false;
}
int main()
{cin>>n>>m>>k;cin>>sx>>sy>>fx>>fy;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>h[i][j];}}if(dfs(sx,sy,0))cout<<"Yes";else cout<<"No";return 0;
}