Submission #1173495

---

Source Code Expand

// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define error(args...) 
#endif

inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

const int WIDTH = 30;
const int HEIGHT = 30;
const int C = 450;
const int TURN = 10000;
int H, W, K, T;
int SX[C], SY[C];
int GX[C], GY[C];

void input() {
    cin >> H >> W >> K >> T;
    REP(i, K) cin >> SY[i] >> SX[i] >> GY[i] >> GX[i];
    REP(i, K) SX[i]--;
    REP(i, K) SY[i]--;
    REP(i, K) GX[i]--;
    REP(i, K) GY[i]--;
}

const int dxs[4] = {1, 0, -1, 0};
const int dys[4] = {0, 1, 0, -1};

int get_move(int dx, int dy) {
    if(dx == 1) {
        return 0;
    } else if(dx == -1) {
        return 2;
    } else if(dy == 1) {
        return 1;
    } else if(dy == -1) {
        return 3;
    } else {
        return 4;
    }
}

string moves_to_str(vector<int> moves) {
    string D = "RDLU-";
    string res;
    REP(i, moves.size()) res += D[moves[i]];
    return res;
}

double calc_score(int X[C], int Y[C], int turn) {
    int diff = 0;
    REP(i, C) diff += abs(X[i] - GX[i]);
    REP(i, C) diff += abs(Y[i] - GY[i]);
    double score = (20.0 + diff) * (10 + 0.01 * turn);
    return score;
}

vector<string> greedy() {
    vector<string> answer;
    int X[C], Y[C];
    REP(i, C) X[i] = SX[i];
    REP(i, C) Y[i] = SY[i];
    vector<double> scores;
    scores.push_back(calc_score(X, Y, 0));
    while(answer.size() < TURN) {
        int NX[C], NY[C];
        bool grid[HEIGHT][WIDTH] = {};
        REP(i, C) grid[Y[i]][X[i]] = true;

        bool updated = false;
        vector<int> moves;

        REP(i, C) {
            const int dx = (X[i] < GX[i] ? 1 : X[i] > GX[i] ? -1 : 0);
            const int dy = (Y[i] < GY[i] ? 1 : Y[i] > GY[i] ? -1 : 0);
            NX[i] = X[i];
            NY[i] = Y[i];
            if(dx != 0 && !grid[Y[i]][X[i] + dx]) {
                NX[i] += dx;
                moves.push_back(get_move(dx, 0));
                grid[NY[i]][NX[i]] = true;
                updated = true;
            } else if(dy != 0 && !grid[Y[i] + dy][X[i]]) {
                NY[i] += dy;
                moves.push_back(get_move(0, dy));
                grid[NY[i]][NX[i]] = true;
                updated = true;
            } else {
                moves.push_back(4);
            }
        }

        if(!updated) break;

        REP(i, C) X[i] = NX[i];
        REP(i, C) Y[i] = NY[i];

        answer.push_back(moves_to_str(moves));
        const int turn = (int)answer.size();
        scores.push_back(calc_score(X, Y, turn));
    }
    int min_score_length = 0;
    for(int i = 0; i < scores.size(); i++) {
        if(scores[min_score_length] > scores[i]) {
            min_score_length = i;
        }
    }
    vector<string> final_answer;
    REP(i, min_score_length) final_answer.push_back(answer[i]);
    cerr << 1e7 / scores[min_score_length] << endl;
    return final_answer;
}

void output(vector<string> answer) {
    cout << answer.size() << endl;
    for(int i = 0; i < answer.size(); i++) {
        cout << answer[i] << endl;
    }
}

int main(){
    iostream_init();

    input();
    auto answer = greedy();
    output(answer);

    return 0;
}

Submission Info

Judge Result