[ACM]poj 1088 滑雪

  • 2015-09-26
  • 0
  • 0

题意:中文题目自己领会
思路:递归+记忆化搜索(DP)
从某点扩散计算路径长度
AC代码:

#include<iostream>
using namespace std;
#define MAX 101
int r, c;
int dp[MAX][MAX];
int board[MAX][MAX];
int find(int x, int y)
{
	if (dp[x][y] != 0)
	{
		return dp[x][y];
	}
	int maxLen = 1;
	if (x + 1 < r&&board[x][y] > board[x + 1][y])
	{
		int len = find(x + 1, y) + 1;
		if (len > maxLen)
		{
			maxLen = len;
		}
	}
	if (x - 1 >=0&&board[x][y] > board[x - 1][y])
	{
		int len = find(x - 1, y) + 1;
		if (len > maxLen)
		{
			maxLen = len;
		}
	}
	if (y + 1 < c&&board[x][y] > board[x][y + 1])
	{
		int len = find(x, y + 1) + 1;
		if (len > maxLen)
		{
			maxLen = len;
		}
	}
	if (y - 1 >= 0 && board[x][y] > board[x][y - 1])
	{
		int len = find(x, y - 1) + 1;
		if (len > maxLen)
		{
			maxLen = len;
		}
	}
	return maxLen;
}
int main()
{
	
	cin >> r >> c;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> board[i][j];
			dp[i][j] = 0;
		}
	}
	int maxLen = 0;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			dp[i][j] = find(i, j);
			if (dp[i][j] > maxLen)
			{
				maxLen = dp[i][j];
			}
		}
	}
	cout << maxLen << endl;
	return 0;
}

评论

还没有任何评论,你来说两句吧