递归——深度优先搜索(DFS)——以滑雪问题为例(自顶而下)
一、问题:滑雪
问题描述:小明喜欢滑雪,为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。小明想知道在一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:
1234 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为
24-17-16-1
. 当然 25-24-23-...-3-2-1
更长。事实上,这是最长的一条.- 输入描述:输入的第一行表示区域的行数 R和列数 C (1 ≤R,C≤100). 下面是 RR 行,每行有 C 个整数,代表高度 h ,0≤h≤10000.
- 输出描述:输出最长区域的长度.
- 样例输入
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
- 样例输出:25
- 简述:从二维数组中,找到一条满足条件(一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小)节点的个数。
- 可以采用DFS算法,搜索出以一个节点为起点,最远可以抵达的地方,并记录长度(其中节点个数)
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
依此输入为例(以21所在位置为起点)
下面展示三张搜索的过程
文章图片
#include#include using namespace std; const int N=105,mod=1e9+7; int a[N][N]; int n,m; int tmp; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int h[N][N]; //记录坐标(i,j)的答案,以(i,j)为起点的路径最长多少 int dfs(int x,int y){//以(x,y)为起点的遍历 int mx=0; if(h[x][y])return h[x][y]; // 记录为0的路径避免重复计算 for(int i=0; i<4; i++){ int nx=x+dx[i],ny=y+dy[i]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny] #include using namespace std; const int N=105,mod=1e9+7; int a[N][N]; int n,m; int tmp; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int h[N][N]; //记录坐标(i,j)的答案,以(i,j)为起点的路径最长多少 int dfs(int x,int y){//以(x,y)为起点的遍历 int mx=0; if(h[x][y])return h[x][y]; // 记录为0的路径避免重复计算 for(int i=0; i<4; i++){ int nx=x+dx[i],ny=y+dy[i]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]
五、递归思想总结六、感悟: 【递归——深度优先搜索(DFS)——以滑雪问题为例(自顶而下)】先将大问题分解成一个基础问题+一个小一层级问题,并用递归模型表示出来,利用图文结合方法加快效率。最后落地。
- 归纳假设:一个节点为起点的最深路径为周围节点最深路径加一
- 递归模型
- f(x,y):路径的长度
- f(x,y)==1 当四周找不到更低的地方(无处可去)(递归出口)
- f(x,y)==max(f(x-1,y),f(x+1,y),f(x,y+1),f(x,y-1))+1(递归体)
推荐阅读
- #|C语言每日一练——第140天(抓交通肇事犯)
- 蓝桥杯真题(C/C++)|题目 1575: 递归倒置字符数组
- 每日leetcode——155. 最小栈
- 蓝桥杯每日一刷|蓝桥杯每日一刷(第六天)——暂会哈希
- Locust1.x 的监控平台——boomer
- PendingIntent重定向(一种针对安卓系统和流行App的通用提权方法——BlackHat EU 2021议题详解(上))
- 『现学现忘』Docker基础|『现学现忘』Docker基础 — 14、Docker的卸载
- 【直播回顾】OpenHarmony知识赋能第四期直播——标准系统HDF开发
- 程序员|【深度思考】普通二本的辛酸Java面试之路,含答案解析
- 『现学现忘』Docker基础|『现学现忘』Docker基础 — 13、通过脚本安装Docker