Submission #1180282

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

#ifdef _WIN32
#include <Windows.h>
#else
#include <sys/time.h>
#endif

class TicToc
{
private:
    double getCurrTime(){
    #ifdef _WIN32
        return GetTickCount() * 1e-3;
    #else
        struct timeval tv;
        gettimeofday(&tv, NULL);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    #endif
    }
    double startTime;
public:
    void tic(){
        startTime = getCurrTime();
    }
    double toc(){
        return getCurrTime() - startTime;
    }
};

unsigned xor128(){
    static unsigned x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

const int dy[] = {-1, 1, 0, 0, 0};
const int dx[] = {0, 0, -1, 1, 0};
const string ds = "UDLR-";

void minDist(const vector<string>& plane, char wall, int y0, int x0, vector<vector<int> >& dist, vector<vector<int> >& prev)
{
    int h = plane.size();
    int w = plane[0].size();
    dist.assign(h, vector<int>(w, -1));
    prev.assign(h, vector<int>(w, -1));

    queue<pair<int, int> > q;
    q.push(make_pair(y0, x0));
    dist[y0][x0] = 0;
    int n = 1;
    while(!q.empty()){
        queue<pair<int, int> > q1;
        while(!q.empty()){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            for(int i=0; i<4; ++i){
                int y1 = y + dy[i];
                int x1 = x + dx[i];
                if(0 <= y1 && y1 < h && 0 <= x1 && x1 < w && plane[y1][x1] != wall && dist[y1][x1] == -1){
                    q1.push(make_pair(y1, x1));
                    dist[y1][x1] = n;
                    prev[y1][x1] = i;
                }
            }
        }
        ++ n;
        q = q1;
    }
}

int getScore(int sy, int sx, const vector<int>& order, const vector<int>& fy, const vector<int>& fx, const vector<int>& f, const vector<int>& d, const vector<vector<vector<vector<int> > > >& dist)
{
    int n = order.size();
    int step = -1;
    int score = 0;
    for(int i=0; i<n; ++i){
        int y = fy[order[i]];
        int x = fx[order[i]];
        step += dist[sy][sx][y][x];
        score += f[order[i]] - d[order[i]] * step;
        sy = y;
        sx = x;
    }
    return score;
}

int main()
{
    TicToc tictoc;
    tictoc.tic();

    int h, w, maxStep, sy, sx;
    cin >> h >> w >> maxStep >> sy >> sx;
    -- sy;
    -- sx;
    vector<string> s(h);
    for(int y=0; y<h; ++y)
        cin >> s[y];

    int n;
    cin >> n;
    vector<int> fy(n), fx(n), f(n), d(n);
    for(int i=0; i<n; ++i){
        cin >> fy[i] >> fx[i] >> f[i] >> d[i];
        -- fy[i];
        -- fx[i];
    }

    vector<vector<vector<vector<int> > > > dist(h, vector<vector<vector<int> > >(w));
    vector<vector<vector<vector<int> > > > prevStep(h, vector<vector<vector<int> > >(w));
    for(int y=0; y<h; ++y){
        for(int x=0; x<w; ++x){
            if(s[y][x] != '#')
                minDist(s, '#', y, x, dist[y][x], prevStep[y][x]);
        }
    }

    vector<int> bestOrder;
    int maxScore = INT_MIN;
    do{
        int y = sy;
        int x = sx;
        int step = -1;
        vector<bool> check(n, false);
        vector<int> order;
        for(int i=0; i<n; ++i){
            vector<tuple<int, int, int> > v(n, make_tuple(INT_MAX, -1, -1));
            for(int j=0; j<n; ++j){
                if(!check[j]){
                    get<0>(v[j]) = dist[y][x][fy[j]][fx[j]];
                    get<1>(v[j]) = xor128();
                    get<2>(v[j]) = j;
                }
            }
            sort(v.begin(), v.end());

            int k = get<2>(v[0]);
            check[k] = true;
            int step2 = step + dist[y][x][fy[k]][fx[k]];
            int score = f[k] - d[k] * step2;
            if(score > 0){
                order.push_back(k);
                y = fy[k];
                x = fx[k];
                step = step2;
            }
        }

        int score = getScore(sy, sx, order, fy, fx, f, d, dist);
        if(maxScore < score){
            maxScore = score;
            bestOrder = order;
        }
    }while(tictoc.toc() < 9.7);

    string ans;
    for(unsigned i=0; i<bestOrder.size(); ++i){
        int y1, x1;
        if(i == 0){
            y1 = sy;
            x1 = sx;
        }
        else{
            y1 = fy[bestOrder[i-1]];
            x1 = fx[bestOrder[i-1]];
        }
        int y2 = fy[bestOrder[i]];
        int x2 = fx[bestOrder[i]];

        string s;
        while(y1 != y2 || x1 != x2){
            int j = prevStep[y1][x1][y2][x2];
            s += ds[j];
            y2 -= dy[j];
            x2 -= dx[j];
        }
        reverse(s.begin(), s.end());
        ans += s;
    }
    ans.resize(maxStep, '-');
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result