#include<iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int a[101][101];
int dp[101][101];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dir[4][2] =
{
{1,0},
{-1,0},
{0,-1},
{0,1}};
int n,k;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int Dfs(int i,int j)//深搜方位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int p,q,s,t,temp,m = 0;
if(dp[i][j] > 0)
return dp[i][j];
for(p = 0;p < 4;p++)//搜四个方向
for(q = 1;q <= k;q++)//一次可以跳1-k步
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
s = i + dir[p][0]*q;
t = j + dir[p][1]*q;
if(s>=1 && s<=n && t>=1 && t<= n && a[i][j] < a[s][t])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
temp = Dfs(s,t);
if(m < temp)//从周围找到最大的数
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
m = temp;
}
}
}
dp[i][j] = m + a[i][j];//本身也要加上
return dp[i][j];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while(cin>>n>>k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(n == -1 && k == -1)
break;
int i,j;
for(i = 1;i <= n;i++)
for(j = 1; j <= n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&a[i][j]);
dp[i][j] = 0;
}
Dfs(1,1);
cout<<dp[1][1]<<endl;
}
return 0;
}