UVa : 10285 (Longest Run on a Snowboard)



// http://uva.onlinejudge.org/external/102/10285.html

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int R, C;
int matrix [100 + 3] [100 + 3];
int dp [100 + 3] [100 + 3];

void reset ()
{
	memset (dp, -1, sizeof (dp));
}

int bktk (int x, int y)
{
	if ( dp [x] [y] != -1 ) return dp [x] [y];

	int up = 0, down = 0, right = 0, left = 0;

	if ( x != 0 && matrix [x - 1] [y] < matrix [x] [y] )
		up = bktk (x - 1, y) + 1;

	if ( x != R - 1 && matrix [x + 1] [y] < matrix [x] [y] ) 
		down = bktk (x + 1, y) + 1;

	if ( y != 0 && matrix [x] [y - 1] < matrix [x] [y] ) 
		left = bktk (x, y - 1) + 1;

	if ( y != C - 1 && matrix [x] [y + 1] < matrix [x] [y] ) 
		right = bktk (x, y + 1) + 1;

	return dp [x] [y] = max (up, max (down, max (right, left)));
}


int main ()
{
	int testCase;
	scanf ("%d", &testCase);

	while ( testCase-- ) {

		reset ();
		char name [100];
		scanf ("%s %d %d", name, &R, &C);
		
		for ( int i = 0; i < R; i++ ) {
			for ( int j = 0; j < C; j++ )
				scanf ("%d", &matrix [i] [j]);
		}

		int maxLen = INT_MIN;

		for ( int i = 0; i < R; i++ ) {
			for ( int j = 0; j < C; j++ ) {
				int len = bktk (i, j);
				if ( len > maxLen ) maxLen = len;
			}
		}

		printf ("%s: %d\n", name, maxLen + 1);
	}

	return 0;
}

// @END_OF_SOURCE_CODE

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