1 //Accepted    468 KB    812 ms 2 //bfs+dp 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 #include <queue> 8 const int imax_n = 105; 9 int map[imax_n][imax_n];10 int dp[imax_n][imax_n];11 bool vis[imax_n][imax_n];12 int d[][2]={1,0,-1,0,0,1,0,-1};13 int n;14 int k;15 queue<int > qx;16 queue<int > qy;17 int max(int a,int b)18 {19     return a>b?a:b;20 }21 void bfs()22 {23     memset(dp,0,sizeof(dp));24     memset(vis,0,sizeof(vis));25     while (!qx.empty()) qx.pop();26     while (!qy.empty()) qy.pop();27     qx.push(0);28     qy.push(0);29     dp[0][0]=map[0][0];30     vis[0][0]=true;31     while (!qx.empty())32     {33         int x=qx.front();34         qx.pop();35         int y=qy.front();36         qy.pop();37         vis[x][y]=false;38         int nx,ny;39         for (int j=0;j<4;j++)40         for (int i=1;i<=k;i++)41         {42             nx=x+i*d[j][0];43             ny=y+i*d[j][1];44             if (nx>=0 && nx<n && ny>=0 && ny<n && map[nx][ny]>map[x][y])45             {46                 if (dp[nx][ny]<dp[x][y]+map[nx][ny])47                 {48                     dp[nx][ny]=dp[x][y]+map[nx][ny];49                     if (!vis[nx][ny])50                     {51                         vis[nx][ny]=true;52                         qx.push(nx);53                         qy.push(ny);54                     }55                 }56             }57         }58     }59     int ans=0;60     for (int i=0;i<n;i++)61     for (int j=0;j<n;j++)62     ans=max(ans,dp[i][j]);63     printf("%d\n",ans);64 }65 int main()66 {67     while (scanf("%d%d",&n,&k) && !(n==-1 && k==-1))68     {69         for (int i=0;i<n;i++)70         for (int j=0;j<n;j++)71         scanf("%d",&map[i][j]);72         bfs();73     }74     return 0;75 }