1078.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 77 行

#include <iostream>
#include <cstring>
using namespace std;
int mm[110][110];
int dp[110][110];
int n, k;
int dfs(int a, int b)
{
	int i, num, a1, b1;
	if (dp[a][b] != 0)
	{
		return dp[a][b];
	}
	num = 0;
	for (i = 1; i <= k; i++)
	{
		a1 = a - i;
		if (a1 > 0 && a1 <= n && mm[a1][b] > mm[a][b])
		{
			dp[a1][b] = dfs(a1, b);
			if (dp[a1][b] > num)
			{
				num = dp[a1][b];
			}
		}
		a1 = a + i;
		if (a1 > 0 && a1 <= n && mm[a1][b] > mm[a][b])
		{
			dp[a1][b] = dfs(a1, b);
			if (dp[a1][b] > num)
			{
				num = dp[a1][b];
			}
		}		
		b1 = b - i;
		if (b1 > 0 && b1 <= n && mm[a][b1] > mm[a][b])
		{
			dp[a][b1] = dfs(a, b1);
			if (dp[a][b1] > num)
			{
				num = dp[a][b1];
			}
		}
		b1 = b + i;
		if (b1 > 0 && b1 <= n && mm[a][b1] > mm[a][b])
		{
			dp[a][b1] = dfs(a, b1);
			if (dp[a][b1] > num)
			{
				num = dp[a][b1];
			}
		}
	}
	return num + mm[a][b];
}
int main()
{
	int i, j;
	while (scanf("%d %d", &n, &k) == 2)
	{
		memset(mm, 0, sizeof(mm));
		memset(dp, 0, sizeof(dp));
		if (n == -1 && k == -1)
		{
			break;
		}
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				scanf("%d", &mm[i][j]);
			}
		}
		cout << dfs(1, 1) << endl;
	}
	return 0;
}