滑雪 why WA

滑雪

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 587 Solved: 219

Description

小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二位数组给出。数组的每个数字代表点的高度。下面是一个例子：

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 24 17 16 1（从25开始到1结束），当然25 24 23 22... 2 1更长，事实上是最长的一条。

Input

多个测试数据。每组测试数据第一行为表示区域的数组的行数R和列数C（ 1 <= R ,C <= 100) 下面是R行，每行有C个数代表高度（不超过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

25

WA:

 #include<stdio.h>

 #define INF -1

 int R,C;

 int Ski_area[][];

 int dp[][];

 int maxn;

 int max(int a,int b)

 {

     return a>b?a:b;

 }

 void ski_high(int x,int y,int *length)

 {

     int j,k,m[];

     m[]=Ski_area[x-][y],m[]=Ski_area[x][y-],m[]=Ski_area[x+][y],m[]=Ski_area[x][y+];

     k=-;

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

         {

             if(Ski_area[x][y]<m[j])

             {

                 if(k==-)

                 {

                     k=j;

                 }

                 else

                 {

                     if(m[k]>m[j])

                         k=j;

                 }

             }

         }

         if(k==-)

             return;

         ++(*length);

         if(k==)

             ski_high(x-,y,length);

         else if(k==)

             ski_high(x,y-,length);

         else if(k==)

             ski_high(x+,y,length);

         else

             ski_high(x,y+,length);

 }

 int main()

 {

     freopen("a.txt","r",stdin);

     int i,j,k;

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

     {

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

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

             {

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

             }

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

         {

             Ski_area[i][]=INF;

         }

         for(i=;i<=C;i++)

         {

             Ski_area[][i]=INF;

         }

         maxn=;

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

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

             {

                 k=;

                 ski_high(i,j,&k);

                 dp[i][j]=k;

                 maxn=max(maxn,dp[i][j]);

             }

     /*    for(i=1;i<=R;i++)

         {

             printf("\n");

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

                 printf("%-4d",dp[i][j]);

         }*/

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

     }

     return ;

 }

AC版：

 #include<stdio.h>

 int dp[][];

 int arr[][];

 int R,C;

 int getHigh(int i,int j)

 {

     if(dp[i][j]>)

     {

         return dp[i][j];

     }

     int max=;

     if(arr[i][j]>arr[i][j-]&&j->=)

     {

         int h=getHigh(i,j-)+;

         if(h>max)

         {

             max=h;

         }

     }

     if(arr[i][j]>arr[i][j+]&&j+<C)

     {

         int h=getHigh(i,j+)+;

         if(h>max)

         {

             max=h;

         }

     }

     if(arr[i][j]>arr[i-][j]&&i->=)

     {

         int h=getHigh(i-,j)+;

         if(h>max)

         {

             max=h;

         }

     }

     if(arr[i][j]>arr[i+][j]&&i+<R)

     {

         int h=getHigh(i+,j)+;

         if(h>max)

         {

             max=h;

         }

     }

     return max;

 }

 int main()

 {

     //freopen("a.txt","r",stdin);

     int i,j;

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

     {

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

         {

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

             {

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

                 dp[i][j]=;

             }

         }

         int res=;

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

         {

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

             {

                 dp[i][j]=getHigh(i,j);

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

                 {

                     res=dp[i][j];

                 }

             }

         }

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

     }

     return ;

 }

巴特西