题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1107
http://acm.hdu.edu.cn/showproblem.php?pid=1078
1、从gird[0][0]出发,每次的方向搜索一下,每次步数搜索一下
for(i=; i<; i++)
{
for(j=; j<=k; j++)
{
int tx=x+d[i][]*j;
int ty=y+d[i][]*j;
if(tx>=&&tx<n&&ty>=&&ty<n&&grid[x][y]<grid[tx][ty])
{
int temp=memSearch(tx,ty);
if(max<temp) max=temp;
}
}
}
2、temp不断更新四个方向和每一步走多远的最优值
#include <cstdio>
#include <string.h>using namespace std;int n;///网格大小
int k;///每次最多移动的步数
int grid[][];///奶酪
int cheese[][];///记忆化搜索///方向
int d[][]= {{-,},{,},{,-},{,}};///记忆化搜
int memSearch(int x,int y)
{
int i,j;
int max=;
if(cheese[x][y]>) return cheese[x][y];
for(i=; i<; i++)
{
for(j=; j<=k; j++)
{
int tx=x+d[i][]*j;
int ty=y+d[i][]*j;
if(tx>=&&tx<n&&ty>=&&ty<n&&grid[x][y]<grid[tx][ty])
{
int temp=memSearch(tx,ty);
if(max<temp) max=temp;
}
}
}
return cheese[x][y]=max+grid[x][y];
}int main()
{
while(scanf("%d%d",&n,&k)&&n!=-&&k!=-)
{
memset(cheese,,sizeof(cheese));
for(int i=; i<n; i++)
{
for(int j=; j<n; j++)
scanf("%d",&grid[i][j]);
}
printf("%d\n",memSearch(,));
}
return ;
}