E - 滑雪 - 秒客网

Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Description

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

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

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

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

Sample Output

 #include<cstdio>

 #include<string.h>

 using namespace std;

 int s[][],dp[][];

 int R,C;

 int max(int a,int b,int c,int d)

 {

     a=a>b?a:b;

     a=a>c?a:c;

     a=a>d?a:d;

     return a;

 }

 int  f(int x,int y)

 {

     if(dp[x][y]>) return dp[x][y];

  int a=,b=,c=,d=;

     if(x->=&&x-<R&&s[x][y]>s[x-][y])

         a=f(x-,y);

     if(x+>=&&x+<R&&s[x][y]>s[x+][y])

         b=f(x+,y);                      //判断一个点的四个方向,能不能走

     if(y->=&&y-<C&&s[x][y]>s[x][y-])

         c=f(x,y-);

     if(y+>=&&y+<C&&s[x][y]>s[x][y+])

         d=f(x,y+);

     dp[x][y]=max(a,b,c,d)+;//取最大值

     return dp[x][y];//返回节点的值

 }

 int main()

 {

     while(scanf("%d%d",&R,&C)!=EOF)

     {

         memset(dp,,sizeof(dp));//清零

         for(int i=;i<R;i++)

             for(int j=;j<C;j++)

                scanf("%d",&s[i][j]);

         for(int i=;i<R;i++)

             for(int j=;j<C;j++)

                dp[i][j]=f(i,j);//计算每个节点

         int m=;

         for(int i=;i<R;i++)

             for(int j=;j<C;j++)

                if(dp[i][j]>m)

                     m=dp[i][j];//求出最长路径

         printf("%d\n",m);

     }

     return ;

 }

E - 滑雪

相关文章