题目链接：D. Explorer Space
思路：记忆化搜索。。。。。。。因为他说k步以内并且回到原点，并且可以走回头路，所以一定是找出到在i,j,k/2步能够到达的位置的最小价值，然后原路返回就是最佳答案。
\(Code:\)
/* -*- encoding: utf-8 -*-
‘‘‘
@File : D.cpp
@Time : 2021/05/14 15:41:43
@Author : puddle_jumper
@Version : 1.0
@Contact : 1194446133@qq.com
‘‘‘
# here put the import lib*/
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#define ch() getchar()
#define pc(x) putchar(x)
#include<stack>
#include<unordered_map>
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define PI acos(-1)
using namespace std;
template<typename T>void read(T&x){
static char c;
static int f;
for(c=ch(),f=1; c<‘0‘||c>‘9‘; c=ch())if(c==‘-‘)f=-f;
for(x=0; c>=‘0‘&&c<=‘9‘; c=ch())x=x*10+(c&15);
x*=f;
}
template<typename T>void write(T x){
static char q[65];
int cnt=0;
if(x<0)pc(‘-‘),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+‘0‘);
}
const int N = 5e2+10;
map<pair<pair<int,int>, pair<int,int> >,int >G;
int n,m,k;
int f[N][N][33];
int b[N][N],s[14][14];
int st[N][N];
int l[] = {0,0,-1,1},r[] = {1,-1,0,0};
int dfs(int idx,int idy,int step){
if(step == 0)return 0;
if(f[idx][idy][step])return f[idx][idy][step];
int ans = 99999999;
rep(i,0,3){
int x = idx + l[i], y = idy + r[i];
if(x > n or x < 1 or y > m or y < 1)continue;
int h = dfs(x,y,step-1);
ans = min(ans,h + G[{{x,y},{idx,idy}}]);
}
return f[idx][idy][step] = ans;
}
void solve(){
int x,y;
read(n);read(m);read(k);
rep(i,1,n){
rep(j,1,m-1)read(x),G[{{i,j},{i,j+1}}] = G[{{i,j+1},{i,j}}] = x;
}
rep(i,1,n-1){
rep(j,1,m)read(y),G[{{i,j},{i+1,j}}] = G[{{i+1,j},{i,j}}] = y;
}
if(k % 2){
rep(i,1,n){
rep(j,1,m)printf("-1 ");pc(‘\n‘);
}return ;
}
rep(i,1,n){
rep(j,1,m){
printf("%d ",dfs(i,j,k/2)*2);
}
pc(‘\n‘);
}
}
signed main(){ solve();return 0; }
D. Explorer Space(Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)题解)
原文：https://www.cnblogs.com/violentbear/p/14770036.html