Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
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
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 2424－1717－1616－11（从 2424 开始，在 11 结束）。当然 2525－2424－2323－\ldots…－33－22－11 更长。事实上，这是最长的一条。
搜索，显而易见。
用dfs显然比较好，因为题目要求的是是一条最长的路径
以17为例：
上面是2，可以走，如果走，17的路径长度=2的路径长度+1（这里的路径长度指的是以这个点为起点的最长路径）
下面是24，不可以走
左面是16，可以走，如果走，17的路径长度=16的路径长度+1
右面是18，不可以走，
再用递归将2和16的情况进行比较，就可以啦！正确性显然
代码如下：
#include<bits/stdc++.h> using namespace std; int a[105][105];//记忆化，记忆路径长度 int mapn[105][105];//地图 int gg[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //上下左右，小心打错 int x,y;//地图大小 int maxn=0;//存储最大长度 int f(int m,int n)//dfs函数 { if(a[m][n]) return a[m][n];//这个点如果被搜索过了，直接返回值，省去了再次查找的时间 a[m][n]=1;//本身也有长度 for(int i=0;i<4;i++) { int mm=m+gg[i][0]; int nn=n+gg[i][1]; if(mm>0&&mm<=x&&nn>0&&nn<=y&&mapn[m][n]>mapn[mm][nn])//不能越界，而且要是下坡 { f(mm,nn);//递归 a[m][n]=max(a[m][n],a[mm][nn]+1);//上面已结释，不多说 } } return a[m][n];//返回长度 } int main() { cin>>x>>y;//输入地图长度 for(int i=1;i<=x;i++) { for(int j=1;j<=y;j++) { cin>>mapn[i][j];//输入 } } for(int i=1;i<=x;i++) { for(int j=1;j<=y;j++) { maxn=max(maxn,f(i,j)); //刷新路径最长长度 } } cout<<maxn;//输出 return 0; }
这题没有什么坑点，只要思路清晰，明白考点就能写出来啦！
撒花~
原文：https://www.cnblogs.com/zhangzhiyuan123/p/12323551.html