Submission #1173761

---

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;
    }
}

char move_to_char(int m) {
    string D = "RDLU-";
    return D[m];
}

int 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]);
    return (20 + diff) * (1000 + turn);
}

struct State{
    State* prev;
    int X[C], Y[C];
    int score;
    void set_score(int turn) {
        score = calc_score(this->X, this->Y, turn);
    }
    bool operator < (const State& s) const {
        return score > s.score; // reversed
    }
};

int zobrist_table[HEIGHT][WIDTH];
void init_zobrist() {
    REP(y, HEIGHT) REP(x, WIDTH) zobrist_table[y][x] = rand();
}

int zobrist_hash(const int X[C], const int Y[C]) {
    int h = 0;
    REP(i, C) h = h ^ zobrist_table[Y[i]][X[i]];
    return h;
}

State next_greedy(State* s, int next_turn) {
    State ns;
    ns.prev = s;
    bool grid[HEIGHT][WIDTH] = {};
    REP(i, C) grid[s->Y[i]][s->X[i]] = true;
    vector<int> perm(C);
    REP(i, C) perm[i] = i;
    random_shuffle(perm.begin(), perm.end());
    for(int i : perm) {
        ns.X[i] = s->X[i];
        ns.Y[i] = s->Y[i];
        const int dx = (ns.X[i] < GX[i] ? 1 : ns.X[i] > GX[i] ? -1 : 0);
        const int dy = (ns.Y[i] < GY[i] ? 1 : ns.Y[i] > GY[i] ? -1 : 0);
        if(dx != 0 && !grid[ns.Y[i]][ns.X[i] + dx]) {
            ns.X[i] += dx;
            grid[ns.Y[i]][ns.X[i]] = true;
        } else if(dy != 0 && !grid[ns.Y[i] + dy][ns.X[i]]) {
            ns.Y[i] += dy;
            grid[ns.Y[i]][ns.X[i]] = true;
        }
    }
    ns.set_score(next_turn);
    return ns;
}

State next_greedy2(State* s, int next_turn) {
    State ns;
    ns.prev = s;
    bool grid[HEIGHT][WIDTH] = {};
    REP(i, C) grid[s->Y[i]][s->X[i]] = true;

    vector<pair<int, int>> ps;
    REP(i, C) ps[i] = make_pair(-abs(s->X[i] - GX[i])-abs(s->Y[i] - GY[i]), i);
    sort(ps.begin(), ps.end());
    REP(i, C) {
        ns.X[i] = s->X[i];
        ns.Y[i] = s->Y[i];
        const int dx = (ns.X[i] < GX[i] ? 1 : ns.X[i] > GX[i] ? -1 : 0);
        const int dy = (ns.Y[i] < GY[i] ? 1 : ns.Y[i] > GY[i] ? -1 : 0);
        if(dx != 0 && !grid[ns.Y[i]][ns.X[i] + dx]) {
            ns.X[i] += dx;
            grid[ns.Y[i]][ns.X[i]] = true;
        } else if(dy != 0 && !grid[ns.Y[i] + dy][ns.X[i]]) {
            ns.Y[i] += dy;
            grid[ns.Y[i]][ns.X[i]] = true;
        }
    }
    return ns;
}


const int MAX_TURN = 100;
const int BEAM_WIDTH = 50;
const int TRY_COUNT = 50;
vector<string> beam_search() {
    priority_queue<State> que[MAX_TURN];
    static State states[MAX_TURN][BEAM_WIDTH];
    int sc[MAX_TURN] = {};
    State first_state;
    REP(i, C) first_state.X[i] = SX[i];
    REP(i, C) first_state.Y[i] = SY[i];

    first_state.set_score(0);
    que[0].push(first_state);

    REP(i, MAX_TURN) {
        cerr << "turn " << i << endl;
        set<int> hashes;
        REP(j, BEAM_WIDTH) {
            if(que[i].empty()) break;

            const int h = zobrist_hash(que[i].top().X, que[i].top().Y);
            if(hashes.count(h)) {
                que[i].pop();
                continue;
            } else {
                hashes.insert(h);
            }
            cerr << sc[i] << endl;

            states[i][sc[i]++] = que[i].top(); que[i].pop();
            State* cur = &states[i][sc[i]-1];
            if(i + 1 < MAX_TURN) {
                REP(k, TRY_COUNT) {
                    State next = next_greedy(cur, i+1);
                    que[i+1].push(next);
                }
            }
        }
    }
    State min_state = first_state;;
    int ans_turn = 0;
    REP(i, MAX_TURN) REP(j, sc[i]) {
        if(min_state.score > states[i][j].score) {
            min_state = states[i][j];
            ans_turn = i;
        }
    }
    vector<string> answers(ans_turn);
    State* cur = &min_state;
    for(int i = ans_turn-1; i >= 0; i--) {
        State* prev = cur->prev;
        for(int j = 0; j < C; j++) {
            answers[i] += string(1, move_to_char(get_move(cur->X[j] - prev->X[j], cur->Y[j] - prev->Y[j])));
        }
        cur = prev;
    }
    for(int i = 0; i < MAX_TURN; i++) {
        cerr << "score " << i << ": " << 1e9 / states[i][0].score << endl;
    }
    cerr << "best_score: " << 1e9 / min_state.score << endl;
    return answers;
};

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();
    init_zobrist();

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

    return 0;
}

Submission Info

Judge Result