POJ 1088 滑雪（动态规划+记忆化搜寻）

POJ 1088 滑雪（动态规划+记忆化搜索）

//动态规划 + 记忆化搜索

#include <cstdio>
#include <cstring>
const int nMax = 107;
int R, C;
int map[nMax][nMax];
int dp[nMax][nMax];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

int fdp(int x, int y)
{
	if(dp[x][y] != 0) return dp[x][y];
	int k;
	for(k = 0; k < 4; ++ k)
	{
		int xx = x + dir[k][0];
		int yy = y + dir[k][1];
		if(xx >= 0 && xx < R && yy >= 0 && yy < C && map[xx][yy] < map[x][y])
		{
			if(dp[x][y] < fdp(xx, yy) + 1)
			{
				dp[x][y] = fdp(xx, yy) + 1;
			}
		}
	}
	if(dp[x][y] == 0) dp[x][y] = 1;
	return dp[x][y];
}

int main()
{
	while(scanf("%d%d", &R, &C) != EOF)
	{
		int i, j;
		int _min = 0x7fffffff;
		
		int x, y;
		for(i = 0; i < R; ++ i)
		{
			for(j = 0; j < C; ++ j)
			{
				scanf("%d", &map[i][j]);
				if(map[i][j] < _min)
				{
					_min = map[i][j];
					x = i;
					y = j;
				}
			}
		}
		memset(dp, 0, sizeof(dp));
		dp[x][y] = 1;
		for(i = 0; i < R; ++ i)
			for(j = 0; j < C; ++ j) fdp(i, j);
		int _max = 0;
		for(i = 0; i < R; ++ i)
			for(j = 0; j < C; ++ j) if(dp[i][j] > _max)
				_max = dp[i][j];
		printf("%d\n", _max);
	}
	return 0;
}