题目连接：

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int maxn=1010; 6 int dp[maxn][maxn]; 7 int p[maxn][maxn]; 8 int n,k; 9 int dir[4][2]={
   0,1,0,-1,1,0,-1,0};10 11 int dfs(int x,int y)12 {13     int ans=0;14     int xx,yy;15     if(!dp[x][y])16     {17         for(int i=1;i<=k;i++)   //最多走k步18         {19             for(int j=0;j<4;j++)20             {21                  xx=x+dir[j][0]*i;22                  yy=y+dir[j][1]*i;23                 if(xx>=1&&yy>=1&&xx<=n&&yy<=n&&p[xx][yy]>p[x][y]) 24                     ans=max(ans,dfs(xx,yy));25             }26         }27         dp[x][y]=ans+p[x][y];28     }29     return dp[x][y];30 }31 int main()32 {33     while(scanf("%d%d",&n,&k)&&(n!=-1&&k!=-1))34     {35         for(int i=1;i<=n;i++)36             for(int j=1;j<=n;j++)37             scanf("%d",&p[i][j]);38         memset(dp,0,sizeof(dp));39         printf("%d\n",dfs(1,1));40     }41 }