递归——深度优先搜索（DFS）——以滑雪问题为例（自顶而下）

一、问题：滑雪

问题描述：小明喜欢滑雪，为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。小明想知道在一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:

?

1 2 3 4 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

　

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为 24-17-16-1 . 当然 25-24-23-...-3-2-1 更长。事实上，这是最长的一条.

 

• 输入描述：输入的第一行表示区域的行数 R和列数 C (1 ≤R,C≤100). 下面是 RR 行，每行有 C 个整数，代表高度 h ,0≤h≤10000.

• 输出描述:输出最长区域的长度.

• 样例输入

　

?

1 2 3 4 5 6

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

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所在位置为起点）

下面展示三张搜索的过程

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

// dfs： 这个算法会尽可能深的搜索树的分支 <br>#include<cstdio> #include<algorithm> 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]<a[x][y]){//递归出口：找不到更低的去处             mx=max(mx,dfs(nx,ny));//递归体：只要能在周围找到能去的路径，递归调用去找能去路径的最大值         }     }     return h[x][y]=mx+1;//最终求出周围路径最大值+1就是（x,y)为起点的最长滑坡长度 } // dfs： 这个算法会尽可能深的搜索树的分支 ,时间复杂度为O（N） int main(){     scanf("%d%d",&n,&m);     for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++){             scanf("%d",&a[i][j]);         }     }     for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++){             dfs(i,j);         }     }     int ans=0;     for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++){             ans=max(ans,h[i][j]);         }     }     printf("%d\n",ans); } int main(){     scanf("%d%d",&n,&m);     for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++){             scanf("%d",&a[i][j]);         }     }     for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++){             dfs(i,j);         }     }     int ans=0;     for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++){             ans=max(ans,h[i][j]);         }     }     printf("%d\n",ans); }

　　

五、递归思想总结

• 归纳假设：一个节点为起点的最深路径为周围节点最深路径加一

• 递归模型

  • 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（递归体）

六、感悟：

先将大问题分解成一个基础问题+一个小一层级问题，并用递归模型表示出来，利用图文结合方法加快效率。最后落地。