题意：给出n*n的二维矩阵，和k，老鼠每次最多走k步，问老鼠从起点(0,0)出发，能够得到的最大的数(即为将每走过一点的数都加起来的和最大)是多少
和上一题滑雪一样，搜索的方向再加一个循环
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<algorithm> 6 using namespace std; 7 8 typedef long long LL; 9 int a[1005][1005],d[1005][1005],n,k; 10 int dir[4][2]={1,0,-1,0,0,1,0,-1}; 11 12 int dfs(int x,int y){ 13 if(d[x][y]) return d[x][y];//如果已经搜过这一点，则直接返回，不用再重复计算 14 int ans=0; 15 for(int j=1;j<=k;j++){ 16 for(int i=0;i<4;i++){ //四个 方向搜 17 int nx=x+dir[i][0]*j; 18 int ny=y+dir[i][1]*j; 19 if(nx<0||nx>=n||ny<0||ny>=n) continue;//越界 20 if(a[x][y]<a[nx][ny]) 21 ans=max(ans,dfs(nx,ny)); 22 } 23 } 24 25 return d[x][y]=ans+a[x][y]; 26 } 27 28 int main() 29 { 30 while(scanf("%d %d",&n,&k)!=EOF&&n!=-1&&k!=-1){ 31 for(int i=0;i<n;i++) 32 for(int j=0;j<n;j++) cin>>a[i][j]; 33 34 memset(d,0,sizeof(d)); 35 36 printf("%d ",dfs(0,0)); 37 } 38 return 0; 39 }