Submission #2090046

---

Source Code Expand

import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;
import std.random, std.datetime, std.container, std.typecons;
import std.math : abs;

enum {
    H = 50,     // 盤面の縦幅
    W = 50,     // 盤面の横幅
    K = 2500,   // 操作列の長さ
}

int N;              // 餌の数
int sr, sc;         // 犬の初期位置
char[][] map;       // 盤面情報
int[][] esa;        // 各cellに何番目の餌があるか（無い場合は-1)
int[] initScore;    // 各餌の初期スコア
int[] dec;          // 各餌の減少スコア/sec
string ans;         // 最終的に出力するコマンド列
int time;           // 現在の時刻

void proc() {
    // コマンド列の長さがK以上になるまで続ける
    int rp = sr, cp = sc;

    while (ans.length < K) {
        // 現在の位置から最も近くてかつ正の得点を持つ餌へ移動する
        // BFSでやる
        auto str = BFS(rp, cp);
        if (str.empty) break;
        ans ~= str;
        time += str.length;
    }

    if (ans.length < K) {
        ans ~= repeat('-', K - ans.length.to!int).to!string;
    }
    ans = ans[0 .. K];
    return;
}

immutable(int[]) dr = [1, 0, -1, 0];
immutable(int[]) dc = [0, 1, 0, -1];
string dir = "DRUL";

// 現在の位置(rp, rc)から最も近い正の餌へたどり着くためのコマンド列を返す
string BFS(ref int rp, ref int rc) {
    alias Pos = Tuple!(int, "r", int, "c", int, "dist");
    auto from = new char[][](H, W);
    fillAll(from, 'x');
    from[rp][rc] = '-';

    auto q = Queue!(Pos)(H*W);

    q.insert(Pos(rp, rc, 0));

    int lastr = -1, lastc = -1;

    while(!q.empty) {
        auto v = q.front;
        q.removeFront();

        foreach (k ; 0 .. 4) {
            int nr = v.r + dr[k];
            int nc = v.c + dc[k];

            if (map[nr][nc] != '#' && from[nr][nc] == 'x') {
                int idx = esa[nr][nc];
                if (idx == -1) {
                    from[nr][nc] = dir[k];
                    q.insert(Pos(nr, nc, v.dist + 1));
                }
                else if (initScore[idx] - dec[idx] * (time + v.dist + 1) >= 0) {
                    from[nr][nc] = dir[k];
                    q.insert(Pos(nr, nc, v.dist + 1));
                    lastr = nr, lastc = nc;
                }
            }
        }

        if (lastr != -1) break;
    }

    if (lastr == -1) {
        return "";
    }

    rp = lastr;
    rc = lastc;

    string res;

    while (from[lastr][lastc] != '-') {
        res ~= from[lastr][lastc];
        esa[lastr][lastc] = -1;

        final switch (from[lastr][lastc]) {
            case 'R':
            lastc--;
            break;

            case 'L':
            lastc++;
            break;

            case 'D':
            lastr--;
            break;

            case 'U':
            lastr++;
            break;
        }
    }

    esa[lastr][lastc] = -1;

    res = res.retro.to!(string);

    debug {
        stderr.writeln("res:", res);
    }

    return res;
}


void input() {
    auto line = readln.split.to!(int[]);
    sr = line[3] - 1, sc = line[4] - 1;

    map = new char[][](H, W);
    foreach (i ; 0 .. H) {
        map[i] = readln.chomp.to!(char[]);
    }

    scan(N);

    initScore = new int[](N);
    dec = new int[](N);
    esa = new int[][](H, W);
    fillAll(esa, -1);

    foreach (i ; 0 .. N) {
        int fr, fc, F, D;
        scan(fr, fc, F, D);
        fr--, fc--;
        esa[fr][fc] = i;
        initScore[i] = F;
        dec[i] = D;
    }
}

void output() {
    assert(ans.length == K);
    writeln(ans);
}

void main() {
    input();
    proc();
    output();
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


struct Queue(T) {
    private {
        size_t cap, head, tail;
        T[] data;
    }

    this (size_t n) in {
        assert(n > 0, "The capacity of a queue must be a positive integer.");
    } body {
        cap = n + 1;
        data = new T[](cap);
    }

    void clear() {
        head = tail = 0;
    }

    bool empty() {
        return head == tail;
    }

    bool full() {
        return head == (tail + 1) % cap;
    }

    size_t length() {
        return head <= tail ? tail - head : cap - head + tail;
    }

    T front() in {
        assert(!empty, "The queue is empty.");
    } body {
        return data[head];
    }

    void removeFront() in {
        assert(!empty, "The queue is empty.");
    } body {
        (++head) %= cap;
    }

    alias popFront = removeFront;

    void insertBack(T x) in {
        assert(!full, "The queue is full.");
    } body {
        data[tail++] = x;
        tail %= cap;
    }

    alias insert = insertBack;

    T[] array() {
        return head <= tail ? data[head .. tail].dup : data[head .. $] ~ data[0 .. tail];
    }

    string toString() {
        import std.format : format;

        if (head <= tail) {
            return format("[%(%s, %)]", data[head .. tail]);
        }
        else {
            return format("[%(%s, %)", data[head .. $]) ~ format(", %(%s, %)]", data[0 .. tail]);
        }
    }
}

Submission Info

Judge Result