1088.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


#define INF 30000

#if debug
    #define NMAX 1
#else
    #define NMAX 101
#endif
int R,C;
int a[NMAX][NMAX]={0};
int high[NMAX][NMAX]={0};

int xp[4]={0,1,0,-1};
int yp[4]={-1,0,1,0}; 
typedef struct 
{
	int h,y,x;
}DATA;
DATA data[NMAX*NMAX];
int cmp(const void *a,const void *b)
{
	return ((DATA*)a)->h-((DATA*)b)->h;
}
int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d%d",&R,&C);
	int i,j;
	int k=0;
	for(i=0;i<R;i++)
		for(j=0;j<C;j++)
		{
			scanf("%d",&high[i][j]);
			data[k].x=j;
			data[k].y=i;
			data[k].h=high[i][j];
			a[i][j]=1;		
			k++;
		}
	qsort(data,R*C,sizeof(DATA),cmp);
	
	int x,y;
	for(i=1;i<R*C;i++)
	{
		x=data[i].x;
		y=data[i].y;
		for(int p=0;p<4;p++)
		{
			if(high[y][x]>high[y+yp[p]][x+xp[p]]&&a[y][x]<a[y+yp[p]][x+xp[p]]+1)
				a[y][x]=a[y+yp[p]][x+xp[p]]+1;
		}
	}


	int max=0;
	for(i=0;i<R;i++)
		for(j=0;j<C;j++)
			if(max<a[i][j])
				max=a[i][j];
	printf("%d",max);
						
#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}