Posted in DFS, Dynamic Programming

PKU 7 Skiing

Problem: http://acmicpc.openjudge.cn/practice/007/


#include<iostream>
#include<cstring>
using namespace std;
int a[105][105] = {0};
int dp[105][105] = {0};
int dx[5] = {-1, 0, 0, 1};
int dy[5] = {0, -1, 1, 0};
int r, c;

int dfs(int x, int y) {
	if (dp[x][y] > 0) {
		return dp[x][y];	
	}	
	int tmp = 0;
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx > 0 && xx <= r && yy > 0 && yy <= c && a[xx][yy] < a[x][y]) {
			tmp = max(tmp, dfs(xx, yy) + 1);
		}
	} 
	return tmp;
}

int main() {
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> a[i][j];
		}
	}
	int mx = 0;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			dp[i][j] = dfs(i, j);
			// cout << dp[i][j] << ' ';
			if (dp[i][j] > mx) {
				mx = dp[i][j];
			} 
		}
		// cout << endl;
	}
	cout << mx + 1;
	return 0;
}

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s