记忆化dp的特征很明显（之前递推学过的记忆化就派上用处）
如果超时就用这个方法改进吧
重要的是我们dp[][]从这个点出发可以吃到的最多奶酪
int mm=g[x][y];
mm=max(mm,g[x][y]+dfs(nx,ny));//没走和走了
出发的概念就是自己和下一步取最大值
#include <bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int g[105][105];
int n,k;
int dp[105][105];//从这个点出发吃到的最大奶酪数
int dfs(int x,int y)
{if(dp[x][y]!=-1) return dp[x][y];int mm=g[x][y];for(int i=0;i<4;i++){for(int step=1;step<=k;step++)//可以× 垂直水平走的 {int nx=x+dx[i]*step;int ny=y+dy[i]*step;if(nx<0||nx>=n||ny<0||ny>=n) continue;if(g[x][y]>=g[nx][ny]) continue;//保障了搜索的但方向性所以不会重复 mm=max(mm,g[x][y]+dfs(nx,ny));//没走和走了 }}return dp[x][y]=mm;
}
int main()
{while(cin>>n>>k){memset(dp,-1,sizeof(dp));if(n==-1 &&k==-1) break;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>g[i][j];}}int ans=dfs(0,0);cout<<ans<<endl;}
}
普通的是
#include <bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int g[105][105];
int n,k;int mm=0;
int visited[105][105];
void dfs(int x,int y,int sw)
{mm=max(mm,sw);for(int i=0;i<4;i++){for(int step=1;step<=k;step++){int nx=x+dx[i]*step;int ny=y+dy[i]*step;int nw=sw+g[nx][ny];if(nx<0||nx>=n||ny<0||ny>=n) continue;if(g[x][y]>=g[nx][ny]) continue;if(visited[nx][ny]) continue;visited[nx][ny]=1;dfs(nx,ny,nw);visited[nx][ny]=0;}}
}
int main()
{while(cin>>n>>k){mm=0;memset(visited,0,sizeof(visited));if(n==-1 &&k==-1) break;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>g[i][j];}}visited[0][0]=1;dfs(0,0,g[0][0]);cout<<mm<<endl;}
}