滑雪
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 ;
}