题意：有n*n大小的网格，每个格子中有一定量的奶酪，一只老鼠从（0，0）开始沿着水平和垂直两个方向走，并且要求目标格子的奶酪数目大于当前格子的奶酪数，每次最多走k格，问到它无法走动时，获得的奶酪的最大数目是多少
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1078
#include<cstdio> #include<cstring> #define Max(a,b) a>b?a:b using namespace std; const int maxn = 1000; int d[maxn][maxn],m[maxn][maxn]; int n,k; bool check(int x,int y) { return (x>=1&&y>=1&&x<=n&&y<=n); } int solve(int x,int y) { int maxv=0; if(d[x][y])return d[x][y]; for(int i=1;i<=k;i++) { if(check(x+i,y)&&m[x][y]<m[x+i][y]) maxv=Max(solve(x+i,y),maxv); if(check(x-i,y)&&m[x][y]<m[x-i][y]) maxv=Max(solve(x-i,y),maxv); if(check(x,y+i)&&m[x][y]<m[x][y+i]) maxv=Max(solve(x,y+i),maxv); if(check(x,y-i)&&m[x][y]<m[x][y-i]) maxv=Max(solve(x,y-i),maxv); } d[x][y] = maxv + m[x][y]; return d[x][y]; } int main() { while(scanf("%d%d",&n,&k)&&(n!=-1||k!=-1)) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&m[i][j]); memset(d,0,sizeof(d)); solve(1,1); printf("%d\n",d[1][1]); } }