深度优先搜索
2021/12/25 23:10:39
本文主要是介绍深度优先搜索,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
深搜
推荐资料:
1、一篇文章完全搞懂深度优先搜索(dfs)(含模板以及例题分析)
2、DFS模板
基本思路:
一条路走到底,不能走就退回上一步,看看有没有别的分支可以走,不断的退回,选择分支。
大概结构:
#include<bits/stdc++.h> using namespace std; int n, m;//n:有几个数 m:要几个 bool used[ ];//是否用过 int ans[ ];//答案 void dfs(int u) { if (出局判断)//到头就走 { 做要做的事 return ;//退出 } for (int i = 开始的地方; i <= n; i++)//从上一个数开始依次增加,枚举每一种情况 { if (used[i] == 0) //判断是否用过 { 加入结果 设为用过 dfs(u + 1);//下一个数字 回溯:回到没用过 } } return ;//退出 } int main() { 输入 初始化 dfs(1);//开始搜索,从1开始 return 0; }
样例代码:
P1434 滑雪
#include<bits/stdc++.h> using namespace std; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int n,m,a[201][201],s[201][201],ans; bool use[201][201]; int dfs(int x,int y) { if(s[x][y]) { return s[x][y]; } s[x][y]=1; for(int i=0;i<4;i++) { int xx=dx[i]+x; int yy=dy[i]+y; if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]) { dfs(xx,yy); s[x][y]=max(s[x][y],s[xx][yy]+1); } } return s[x][y]; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ans=max(ans,dfs(i,j)); } } cout<<ans; return 0; }
这篇关于深度优先搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行