学步园

记忆化搜索，每次可以横着走或竖着走，有四个方向可以走。每次可以走1 - k个格子。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int const MAXN = 110;
int m[MAXN][MAXN],dp[MAXN][MAXN];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
inline int Max(int a,int b){
    return a>b?a:b;
}
int Dfs(int s,int t,int n,int k){
    if(dp[s][t]) return dp[s][t];
    int ss = 0,sss = 0;
    for(int i = 1;i <= k;i++){
        for(int j = 0;j < 4;j++){
            int x = s + dx[j] * i;
            int y = t + dy[j] * i;
            if(x < 1 || x > n || y < 1 || y > n || m[s][t] >= m[x][y]) continue;
            sss = Dfs(x,y,n,k);
            ss = Max(ss,sss);
        }
        dp[s][t] = Max(dp[s][t],ss + m[s][t]);
    }
    return dp[s][t];
}
int main(){
    int n,k;
    while(~scanf("%d%d",&n,&k)){
        if(n == -1 && k == -1) break;
        memset(dp,0,sizeof(dp));
        memset(m,0,sizeof(m));
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                scanf("%d",&m[i][j]);
            }
        }
        Dfs(1,1,n,k);
        int s = 0;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                s = Max(s,dp[i][j]);
            }
        }
        printf("%d\n",s);
    }
    return 0;
}