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