D. Explorer Space
题意：给一个矩阵，告诉你每点相邻边的花费，求每个点k步后回到原点的最短距离。
题解：首先当k为奇数时，一定回不到原点直接输出-1。当k为偶数时，可以理解为该点用了k/2步走了出去，又用k/2步走了回来，易知要距离最短所以出去和回来的路径一定一样，所以题目就转化为了，走k/2步最少能用多少花费，直接记忆化即可。
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
const ll N=507;
const ll inf=1e18;
ll n,m,k,a[N][N],b[N][N],d[N][N][4],f[N][N][17];
ll dx[]={0,0,-1,1};
ll dy[]={1,-1,0,0};
ll dfs(ll x,ll y,ll k){
if(k==0){
return 0;
}
ll mi=inf;
if(f[x][y][k]!=-1){
return f[x][y][k];
}
for(int i=0;i<4;i++){
ll tx=x+dx[i];
ll ty=y+dy[i];
if(1<=tx&&tx<=n&&1<=ty&&ty<=m){
mi=min(mi,dfs(tx,ty,k-1)+d[x][y][i]);
}
}
return f[x][y][k]=mi;
}
ll gao(ll x,ll y){
if(k%2==1){
return -1;
}
else{
return dfs(x,y,k/2)*2;
}
}
int main(){
memset(f,-1,sizeof(f));
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
scanf("%lld",&a[i][j]);
d[i][j][0]=a[i][j];
d[i][j+1][1]=a[i][j];
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
scanf("%lld",&b[i][j]);
d[i][j][3]=b[i][j];
d[i+1][j][2]=b[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%lld ",gao(i,j));
}puts("");
}
}