uva10285 - Longest Run on a Snowboard（記憶化搜索）

uva10285 - Longest Run on a Snowboard（記憶化搜索）

題目：uva10285 - Longest Run on a Snowboard（記憶化搜索）

題目大意：給出N * N的矩陣，要求找到一條路徑，路徑上的值是遞減的，求這樣的路徑的最長長度。

解題思路：記憶話搜索。因為要求最長的路徑那麼就需要將所有的這樣的路徑找出，但是直接dfs會超時的。對於同一個位置，從這個點出發的最長路徑長度是固定的。所以在找的時候就要將這個位置的最長路徑算出來並且保存下來。一開始還擔心會走回頭路就是一直兜圈子。但是後面發現能往右走就不可能在從右邊的那個位置走回去，因為路徑上的值是要求遞減的。

dp【x】【y】代表從x，y這個位置開始能夠走的最長的路徑長度。

代碼：

#include 
#include 

const int N = 105;
const int M = 4;
const int dir[M][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

int G[N][N];
int dp[N][N];
char name[N * 10];
int r, c;

int Max (const int a, const int b) { return a > b? a: b; }

int DP (int x, int y) {

	int& ans = dp[x][y];
	if (ans != -1)
		return ans;
	int newx, newy;
	for (int i = 0;  i < M; i++) {
		newx = x + dir[i][0];
		newy = y + dir[i][1];
		if (newx < 0 || newx >= r || newy < 0 || newy >= c)
			continue;
		if (G[x][y] > G[newx][newy])
			ans = Max (ans, DP (newx, newy) + 1);  //從這個位置開始四個方向的最長長度取最大值 
	}
	if (ans == -1)      //這個點走不出去
		ans = 1;
	return ans;	
}

int main () {
	
	int t;
	scanf ("%d", &t);
	while (t--) {

		scanf ("%s%d%d", name, &r, &c);
		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++)
				scanf ("%d", &G[i][j]);
		
		memset (dp, -1, sizeof (dp));
		int ans = -1;

		for (int i = 0; i < r; i++) 從每個位置開始走都是有可能的取得最長路徑
			for (int j = 0; j < c; j++)
				ans = Max (ans, DP(i, j));
		printf ("%s: %d\n", name, ans);	
	}
	return 0;
}