| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一个思想简单的方法~ 16ms 递归~(仅供参考)#include<stdio.h>
int a[101][101];//用于记录某点的高度
int b[101][101];//用于记录从某点开始的最大坡长
int c[101][101];//用于标记某点是否递归过
int digui(int i,int j)//每一个点都和其上下左右比较:上(i,j-1),下(i,j+1),左(i-1,j),右(i+1,j)
{
if(c[i][j]==1)//如果这个点已经递归过了,就直接返回结果
{
return b[i][j];
}
//如果这个点没有递归过,则动态规划,从周边点中选择最长的
if(a[i][j]>a[i][j-1]&&(1+digui(i,j-1))>b[i][j])
{
b[i][j]=1+digui(i,j-1);
}
if(a[i][j]>a[i][j+1]&&(1+digui(i,j+1))>b[i][j])
{
b[i][j]=1+digui(i,j+1);
}
if(a[i][j]>a[i-1][j]&&(1+digui(i-1,j))>b[i][j])
{
b[i][j]=1+digui(i-1,j);
}
if(a[i][j]>a[i+1][j]&&(1+digui(i+1,j))>b[i][j])
{
b[i][j]=1+digui(i+1,j);
}
c[i][j]=1;//标记该点已经递归过了
return b[i][j];
}
void main()
{
int h,lie,i,j,max,t;
scanf("%d%d",&h,&lie);
for(i=0;i<=100;i++)//初始化
{
for(j=0;j<=100;j++)
{
a[i][j]=50000;//将所有点的高度初始化为无限大,则比较时可忽略边界情况,简化函数
b[i][j]=1;//将每点的长度初始化为1
c[i][j]=0;//0为此点还未递归过
}
}
for(i=1;i<=h;i++)
for(j=1;j<=lie;j++)
scanf("%d",&a[i][j]);
max=1;
for(i=1;i<=h;i++)//递归所有点,找到最大的
{
for(j=1;j<=lie;j++)
{
t=digui(i,j);
if(t>max)
max=t;
}
}
printf("%d",max);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator