UVA – 10285 – Longest Run on a Snowboard   Leave a comment


#include <stdio.h>
int map[105][105];
int dp[105][105];
int n,m;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int max(int a,int b)
{
	return (a>b)?a:b;
}
int longestRun(int i,int j)
{
	if(dp[i][j]!=-1)
		return dp[i][j];
	else
	{
		int res = 0;
		int d,x,y;
		for(d=0;d<4;d++)
		{
			y = i + dy[d];
			x = j + dx[d];
			if(x>=0&&y>=0&&y<n&&x<m&&map[y][x]<map[i][j])
				res = max(res,1+longestRun(y,x));
		}
		return dp[i][j]=res;
	}
}
int main()
{
	int N,r,c,i,j,mx;
	char area[20];
	scanf("%d",&N);
	while(N--)
	{
		scanf("%s %d %d",area,&r,&c);
		n = r;
		m = c;
		for(i=0;i<r;i++)
			for(j=0;j<c;j++)
			{
				scanf("%d",&map[i][j]);
				dp[i][j]=-1;
			}
		mx = 0;
		for(i=0;i<r;i++)
			for(j=0;j<c;j++)
				mx = max(mx,longestRun(i,j));
		printf("%s: %d\n",area,mx+1);
	}
	return 0;
}
Advertisements

Posted August 19, 2011 by epicrado in DAG

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: