写点什么

dfs 专项练习题

作者:秋名山码民
  • 2022 年 5 月 20 日
  • 本文字数:1162 字

    阅读完需:约 4 分钟

碎碎念

dfs,bfs 为何放到最前面?万物皆可暴力,蓝桥杯开始也被称之为暴力杯,开始学习暴力算法,等到后面 dp 不会的时候也可以用暴力求解,<font color=red>蓝桥评分规则:与 acm 有很大的不同, 它是根据题解代码通过的测试点给分, 所以在不会的时候可以用暴力来进行骗取一定的分数


讲了这么多应该能明白 bf 算法对于彦祖们临时抱佛脚的重要性了吧



由于我已经写过一篇 bfs 和 dfs, 我们直接进行题目训练搜索算法dfs和bfs解析(附有例题)老规矩: 用🍺来表示题目难度系数

🍺[求先序排列]


一点基本常识,给你一个后序遍历,那么最后一个就是根


#include<cstdio>#include<iostream>#include<cstring>using namespace std;void beford(string in,string after){    if (in.size()>0){        char ch=after[after.size()-1];        cout<<ch;//找根输出        int k=in.find(ch);        beford(in.substr(0,k),after.substr(0,k));        beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树;    }}int main(){    string inord,aftord;    cin>>inord;cin>>aftord;//读入    beford(inord,aftord);cout<<endl;    return 0;}
复制代码

高手去散步


#include<bits/stdc++.h>using namespace std;int n,m; int mp[25][55];bool vis[25];int ans,s; void dfs(int x,int y){//搜索 ,x,y是这两个景点   if(vis[y]){//当我们发现这个景点来过时,我们就可以存下答案了     jie:    ans=max(ans,s);  //只存最大的路程     return ;//回到上一步看看有没有更优解   }  for(int i=1;i<=n;i++){//遍历数组     if(!vis[x]&&mp[y][i]!=0){//如果这个景点我们没有来过,且我们找到了与之联通的点       s+=mp[x][y];    //暂存变量s先存下我们走过的路程       vis[x]=1;       //标记我们来过这个景点       dfs(y,i);      //进行递归,将下个联通点存入       s-=mp[x][y];      vis[x]=0;    //回溯     }  }  for(int i=1;i<=n;i++){//这一部分是针对绝路的,就是这个景点只有一个景点与之相连,到了死路不能往下再走了     if(mp[y][i]!=0)  //如果发现不是死路就跳出     break;    else if(i==n){  //遍历完地图发现是死路,s就加上当前走过的路程       s+=mp[x][y];      goto jie;  //直接跳入到 ans的判断中     }  }}
int main(){ cin>>n>>m; for(int i=1;i<=m;i++){//将景点与景点之间的距离用一个数组去存 int a,b; cin>>a>>b; cin>>mp[a][b]; mp[b][a]=mp[a][b]; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(mp[i][j]!=0){//如果这个数组不为空就去搜索 dfs(i,j); memset(vis,0,sizeof(vis));//清空标记 s=0;//将暂存变量S清零 } } } cout<<ans; return 0;}
复制代码


发布于: 刚刚阅读数: 2
用户头像

卷不死,就往…… 2021.10.19 加入

2019NOIP退役成员,华为云享专家,阿里云专家博主,csdn博主,努力进行算法分享,有问题欢迎私聊

评论

发布
暂无评论
dfs专项练习题_DFS_秋名山码民_InfoQ写作社区