Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一个思想简单的方法~ 16ms 递归~(仅供参考)

Posted by zhangmytf at 2009-05-28 11:38:01 on Problem 1088 and last updated at 2009-05-28 11:38:55
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator