题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1078
题意是给了两个数n和k,表示有n*n的地图,地图的每个点都有一个权值,有一只老鼠从0,0开始吃奶酪,它可以走上下左右四个方向,一次可以移动1到k个单位,而且每次移动的权值都要比上一次的权值大,最后输出一个最大值。
算是记忆化搜索的入门题了吧,和poj那道滑雪差不多,爆搜的话会有很多重复搜索,肯定会超时,所以还是需要用dp数组来标记,因为每次可以走1到k个单位,所以在遍历4个方向的同时也要遍历每次走的单位长度。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 105
using namespace std;
int MAP[maxn][maxn],dp[maxn][maxn];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int n,m,ans;
bool Check(int x,int y){
if(x >= 0 && y >= 0 && x < n && y < n)return true;
return false;
}
int dfs(int x,int y){
if(dp[x][y])return dp[x][y];
int sum = 0;
for(int i=0;i<4;i++){
for(int j=1;j<=m;j++){
int X = x + dir[i][0] * j;
int Y = y + dir[i][1] * j;
if(Check(X, Y) && MAP[X][Y] > MAP[x][y]){
sum = max(sum,dfs(X,Y));
}
}
}
dp[x][y] = sum + MAP[x][y];
return dp[x][y];
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n == -1 && m == -1)break;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&MAP[i][j]);
}
}
memset(dp,0,sizeof(dp));
ans = dfs(0, 0);
printf("%d\n",ans);
}
return 0;
}