时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子：
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的滑坡为25-24-17-16-1（从25开始到1结束），当然25-24……2-1更长，事实上这是最长的一条。
【输入】
输入的第一行为表示区域的二维数组的行数R和列数C（1≤R、C≤100），下面是R行，每行有C个数代表高度。
【输出】
输出区域中最长的滑坡长度。
【输入样例】
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
1. #include <iostream> 2. #include <cstdio> 3. using namespace std; 4. int dx[5]={0,-1,0,1,0}; 5. int dy[5]={0,0,1,0,-1}; 6. int r,c; 7. long long m[105][105],f[105][105]; 8. long long search(int x,int y){//求到[x,y]点的最长路径 9. if(f[x][y]>0) return f[x][y]; //此点长度已经求出 不必进一步递归 10. long long nx,ny,temp,t=1; 11. for(int i=1;i<=4;i++){ 12. nx=x+dx[i]; 13. ny=y+dy[i]; 14. if((nx>=1)&&(nx<=r)&&(ny>=1)&&(ny<=c)&&(m[x][y]<m[nx][ny])){ 15. temp=search(nx,ny)+1; 16. if(temp>t) t=temp; 17. } 18. } 19. f[x][y]=t;//记忆化存储 20. return t; 21. } 22. int main() 23. { 24. cin>>r>>c; 25. for(int i=1;i<=r;i++) 26. for(int j=1;j<=c;j++) cin>>m[i][j]; 27. long long t,ans=0; 28. for(int i=1;i<=r;i++)//按照行的顺序 逐点求出区域中到达此点的最长路径 29. for(int j=1;j<=c;j++){ 30. t=search(i,j); 31. f[i][j]=t; 32. if(t>ans) ans=t;//更新最大长度 33. } 34. cout<<ans<<endl; 35. return 0; 36. }
