首页 > 其他 > 详细

D. Explorer Space(Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)题解)

时间:2021-05-15 00:41:09      阅读:28      评论:0      收藏:0      [点我收藏+]

题目链接: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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!